二分搜索技术

二分搜索技术

给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

分析：该问题的规模缩小到一定程度就可以容易地解决。而且该问题满足分治法的适用条件：

1. 该问题可以分解为若干个规模较小的相同问题；
2. 分解出的子问题的解可以合并为原问题的解；
3. 分解出的各个子问题是相互独立的。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

int binarySearch(int nums[],int left,int right,int x)
{
	while(left<=right)
	{
		int medium=(left+right)/2;
		if(nums[medium]>x)
			return binarySearch(nums,left,medium-1,x);
		else if(nums[medium]<x)
		    return binarySearch(nums,medium+1,right,x);
		else
			return medium;
	}
	return -1;
}

二分搜索技术是一种非常简单的分治策略，充分利用了元素间的次序关系，可在最坏的情况下用O(log n)完成搜索任务。