折半查找

给定一个整数X和整数A₀，A₁，…，A_N-1，后者已经预先排序并在内存中，求下标i使得A_i = X ， 如果X不在数据中则返回i = -1 。

明显的解法是从左往右扫描，花费线性时间。但是这个算法没有用到该表已经排序这个事实。

折半检索（binary search，二分法检索）策略：

/**
 * Performs the standard binary search.
 *@return index where item is found, or -1 if not found.
 */
 public static <AnyType extends Comparable<? super AnyType>>
 int binarySearch( AnyType [] a , AnyType x )
 {
	int low = 0 ; high = a.length - 1 ; 
	while(low <= high )
	{
		int mid =(low + high)/2;
		if(a[mid].compareTo(x)<0)
			low = mid +1 ; 
		else if (a[mid].compareTo>0)
			high = mid -1 ; 
		else return mid ;//Found
	}
	return NOT_FOUND ; //NOT_FOUND is defined as -1 ; 
 }

　　复杂度为O(logN)。