二分查找（折半查找）

  二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

算法复杂度为o（log（n））

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

写代码可以在整型有序数组中查找想要的数字，找到了返回下标，找不到返回-1.（折半查找） 

第一种方法：（非递归）

int search(int arr[], int left, int right, int key)
{
	int mid = 0;
	while(left<=right)
	{
		mid = (left+right)>>1;
		if(key == arr[mid])
		{
			return mid;
		}
		else if(key > arr[mid])
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	return -1;
}

第二种方法：（递归）

int search0(int arr[], int left, int right, int key)
{
	int mid = 0;
	if(left>right)
	{
		return -1;
	}
	else
	{
		mid = (left+right)>>1;
		if(arr[mid] > key)
		{
			return search0(arr, left, mid-1, key);
		}
		else if(arr[mid] < key) 
		{
			return search0(arr, mid+1, right, key);
		}
		else
		{
			return mid;
		}
	}
}