Binary Search 二分查找,二分搜索 C++

// BSearch.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

template <class T>
void PrintfNum(T a[],const int& n);

/**
* search n in a[], return the index, if not find, return -1.
*/
template <class T>
int BSearch(T a[],const int& length,const int& n){
	int left = 0, right = length - 1;
	while(left <= right){
		int middle = (left + right) / 2;

		//cout << "middle:" <<middle << " ,left:" << left << " ,right:" << right << endl;
		if(n < a[middle]){
			right = middle - 1;
		}else if(n > a[middle]){
			left = middle + 1;
		}else{
			return middle;
		}
	}
	return -1;
}
/**
* A better one
* search n in a[], return the index, if not find, return -1.
*/
template <class T>
int BetterBSearch(T a[],const int& length,const int& n){

	int left = -1, right = length - 1;
	while(left+1 != right){  //left < right && a[left] < n <= a[right]
		int middle = (left + right) / 2;
		if(a[middle] < n){      //a[left] < n
			left = middle;
		}else{                  //a[right] >= n
			right = middle;
		}
	}
	if(right >= length || a[right] != n )//no find
		return - 1;
	return right;
}

/**
* Test function
*/
bool TestBSearch(){
	const int NUM = 20;
	int BeginNum = 10;
	int t[NUM];
	for(int i = 0; i< NUM; ++i){
		t[i] = BeginNum;
		++BeginNum;
	}
	bool result = true;
    for(int j = 0 ;j < NUM; ++j){
		if(BSearch(t, NUM , t[j]) != j){
			result = false;
		}
	}
	// test no find
	if(BSearch(t,NUM,t[0] - 1) != -1 || BSearch(t,NUM,t[NUM-1] + 1) != -1){
		result = false;
	}
	return result;
}

/**
* Test function
*/
bool TestBetterBSearch(){
	const int NUM = 20;
	int BeginNum = 10;
	int t[NUM];
	for(int i = 0; i< NUM; ++i){
		t[i] = BeginNum;
		++BeginNum;
	}
	bool result = true;
    for(int j = 0 ;j < NUM; ++j){
		if(BetterBSearch(t, NUM , t[j]) != j){
			result = false;
		}
	}
	// test no find
	if(BetterBSearch(t,NUM,t[0] - 1) != -1 || BetterBSearch(t,NUM,t[NUM-1] + 1) != -1){
		result = false;
	}
	return result;
}

int main(int argc, char* argv[])
{
	const int NUM = 10;
	int t[NUM] = {10,11,12,13,14,15,16,17,18,20};

	PrintfNum(t,NUM);

	for(int i = 0 ;i < NUM; ++i){
       cout << t[i] << " was at index: " << BSearch(t, NUM , t[i]) << endl; 
	}
	cout << "searching 100 in array t, result: "<< BSearch(t, NUM , 100) << endl;

	cout << endl;
	cout << "BSearch test result:" << TestBSearch() << endl;

	cout << "BetterBSearch test result:" << TestBetterBSearch() << endl;
	return 0;
}

template <class T>
void PrintfNum(T a[],const int& n){
	for(int i = 0; i < n; ++i){
		cout << a[i] << ",";
	}
	cout << endl;
}

http://www.waitingfy.com/?p=464

数据结构 & 算法 | RSS 2.0 | Respond | Trackback |