算法 | 对分查找

【算法思想】

首先将关键字与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。

使用前提：数据有序

【算法实例】

在包含8个数字的数组中用对分法查找一个符合要求的数“24”。

源数据：

第一步、排序：

第二步、在8个数组元素中找出中间数与“24”比较：

             中间数组元素下标＝Int（（最小数组元素下标＋最大数组元素下标）／2）

             中间数组元素下标＝Int（（1＋8）／2）＝4

             d(4)＝34

            ∵ 34＞24

            ∴ 从d(4)开始向后的数据都可以舍弃，要找的“24”必定不在其中。

第三步、在剩下的d(1)到d(3) 间继续找“24”：

             中间数组元素下标＝Int（（1＋3）／2）＝2

             d(2)＝12

             ∵ 12＜24

             ∴ 从d(2)开始向前的数据都可以舍弃，要找的“24”必定不在其中。

第四步、在剩下的d(3)到d(3) 间继续找“24”：

            中间数组元素下标＝Int（（3＋3）／2）＝3

            d(3)＝24

            ∵ 24＝24

            ∴ 找到所需数据在数组中的位置为d(3)

VB程序：

i = 1 ：j = n : s = 0

Do while i <= j

        m = ( i + j ) / 2

        If a( m ) = key Then s = m : Exit Do

        If a( m ) < key Then j = m - 1 

        If a( m ) > key Then i = m + 1

Loop