二分查找（Binary Search）又称折半查找。二分法查找只适合于有序数列。这种方法是将待查找的有序数列不断地分为两部分，将要查找的数据与中心分隔点数据进行比较，判断要查找的内容在这两个部分的哪一段，然后淘汰数据不可能存在的那一半继续查找。它是一种效率较高的查找方法。

假设一维数组a[]存放的是个递增的有序数列，二分法查找的基本思想如下。

1）对要查找的区间，设定区间的左右边界：low～high。

2）将这个区间折半，确定该区间的中点位置：mid=（low+high）/2。

3）将待查的值value与mid的位置元素a[mid]进行比较：若相等，则查找成功，mid即要找的位置；否则，确定新的查找区间。

4）若value＜a[mid]，则又表明要查找的数在位置mid的左边，这时，将区间的mid作为继续查找的区间的右边界：high=mid。

5）若value＞a[mid]，则又表明要查找的数在位置mid的右边，这时，将区间的mid作为继续查找的区间的左边界：low=mid。

6）转步骤2，按新的左右边界，重新查找。

因此，从初始的查找区间[0，n-1]开始，每经过一次与当前查找区间的中点位置上的结点值的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。重复这一过程直至找到值为value的元素位置为止。如果查找区间的左边界最终到达或超过右边界（low＞high），说明查找失败，数组中不存在所要查找的内容。

和线性查找相比较，二分法不需要对数组中的每个数进行查找，效率要高许多。(www.daowen.com)

【例9-14】使用二分法，找出一个有序数组中的某个数的位置。

程序思路：将数组a的0和a.length-1作为区间的左右边界，然后进行对半查找。

程序运行结果：

5

【例9-15】使用递归方法实现二分查找。

程序思路：使用递归方法进行二分查找，可以利用对半分割将n个元素的序列分解为较小规模的n/2，重新设定左右边界，将其中的可能的一半作为子序列进行递归。递归的出口有两个，一个是查找到数值，另一个出口是左右边界重合，说明查找失败。

程序运行结果：

5