算法要求

1、必须采用；

2.必须按关键字大小有序排列。

算法复杂度

假设其 长度为n，其算法复杂度为o（log（n））

下面提供一段二分查找实现的 :

BinarySearch(max,min,des)

mid-<(max+min)/2

while(min<=max)

mid=(min+max)/2

if mid=des then

return mid

elseif mid >des then

max=mid-1

else

min=mid+1

return max

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

 

代码示例

 

JAVA代码

1 public static int binarySearch(Integer[] srcArray, int des) { 2     int low = 0; 3     int high = srcArray.length - 1; 4   5     while ((low <= high) && (low <= srcArray.length - 1) 6             && (high <= srcArray.length - 1)) { 7         int middle = low + ((high - low) >> 1); 8         if (des == srcArray[middle]) { 9             return middle;10         } else if (des < srcArray[middle]) {11             high = middle - 1;12         } else {13             low = middle + 1;14         }15     }16     return -1;17 }