二分搜索技术

             二分搜索算法是运用分治策略的典型例子。

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

             首先较易想到的是用顺序搜索方法，逐个比较a[0:n-1]中元素，直至找出元素x或搜索遍整个数组后确定x不在其中。这个方法没有很好地利用n个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要O(n)次比较。

             二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O(logn)时间完成搜索任务.

             二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。如果x=a[n/2]，则找到x，算法终止。如果x<a[n/2],则只要在数组a的左半部继续搜索x。如果x>a[n/2]，则只要在数组a的右半部继续搜索x

具体算法demo如下：

 

package Recursive;
/**
 * 递归与分治策略-二分搜索
 */
public class er_fen_Search
{
	public static int binarySearch(int []a,int x)
	{
		//在a[0]<=a[1]<=...<=a[n-1]中搜索x
		//找到x时返回其在数组中的位置，否则返回-1
		int left=0;int right=a.length-1;
		while(left<=right)
		{
			int middle=(left+right)/2;
			if(x==a[middle]) return middle;
			if(x>a[middle]) left=middle+1;
			else right=middle-1;
		}
		return -1;//为找到
	}
	public static void main(String[] args)
	{
		int a[] ={1,2,3,4,5,6,7,8,9,10};
		int find = er_fen_Search.binarySearch(a, 2);
		System.out.println(find >= 0 ? "找到数值索引" + find : "找不到数值" );
	}
}

  查找2在数组的位置 

  运行结果为：

找到数值索引1

 

 

 

              容易看出，每执行一次算法的while循环，待搜索数组的大小减小一半，因此在最坏情况下，while循环被执行了O(logn)次，循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。