非递归二分查找算法

BinSearch.cpp

#include <iostream>
using namespace std;

/**
 *   非递归二分查找
 *   @author Boychenney
 *   @date   2013-10-24T11:02:43+0800
 *   @param  r 数组指针		
 *   @param  n 数组大小
 *   @param  k 待查找的值
 *   @return 数组下标
 */
int BinSearch1(int r[],int n,int k){
	int low = 0;
	int high = n;
	int mid = -1;
	while(low<=high){
		mid = (low+high)/2;
		if (k<r[mid]) high = mid - 1;
		else if (k>r[mid]) low = mid + 1;
		else return mid;
	}
	return -1;
};

int BinSearch2(int r[],int low,int high,int k){
	int mid = -1;
	if(low>high) return -1;
	else{
		mid = (low+high)/2;
		if(k<r[mid]) return BinSearch2(r,low,mid-1,k);
		else if(k>r[mid]) return BinSearch2(r,mid+1,high,k);
		else return mid;
	}
}

int main(){
	int arr[13] = {7,14,18,21,23,29,31,35,38,42,46,49,52};
	int len = 13;
	cout<<"first method:"<<BinSearch1(arr,len,31)<<endl;
	cout<<"second method:"<<BinSearch2(arr,0,len-1,21)<<endl;
	return 0;
}