二分查找法（遞歸+循環）

 二分查找法，它的使用前提是數列是有序的，思想就是呢，先給中間的數做個标記，如果你要找的值比它小呢，你就往左找咯，反之亦然，然後再找中間數，一直重複啦~

#include<iostream>
using namespace std;

//遞歸
int Search(int *arr,int left,int right,int key)
{
	int pos = -1;
	int mid = (right - left)/2 + left;
	if(left <= right)
	{
		if(arr[mid] > key)
		{
			pos =  Search(arr,left,mid-1,key);
		}
		else if(arr[mid] < key)
		{
			pos =  Search(arr,mid+1,right,key);
		}
		else
		{
			pos = mid;
		}
	}
	return pos;
}

int Search(int *arr,int len,int key)
{
	if(arr==NULL && len<=0 )
	{
		return -1;
	}
	return Search(arr,0,len-1,key);
}

循環/
int Find(int *arr,int len,int key)
{
	if(arr==NULL || len<0)
	{
		return -1;
	}
	int left = 0;
	int right = len-1;
	int pos = -1;
	while(left <= right)
	{
		int mid = (right - left)/2 + left;
		if(arr[mid] < key)
		{
			left = mid + 1;
		}
		else if(arr[mid] > key)
		{
			right = mid - 1;
		}
		else
		{
			pos = mid;
			break;
		}
	}
	return pos;
}

int main()
{
	int arr[] = {0,1,2,10,21,22,23,45,56,89,101};
	int len = sizeof(arr)/sizeof(arr[0]);
	cout<<Search(arr,len,0)<<endl;
    cout<<Search(arr,len,44)<<endl;
    cout<<Search(arr,len,56)<<endl;
    cout<<Search(arr,len,101)<<endl;

	cout<<Find(arr,len,0)<<endl;
    cout<<Find(arr,len,44)<<endl;
    cout<<Find(arr,len,56)<<endl;
    cout<<Find(arr,len,101)<<endl;

	return 0;
}