查找算法之 '二分法查找'

二分法查找

二分法查找适用于数据量较大时，但是数据需要先排好顺序。

算法原理

一维有序数组，折半查找

假如有一组数为3，12，24，36，55，68，75，88 要查给定的值24，可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）// 2 。

1、开始令 front=0（指向3），end=7（指向88），则mid=3（指向36） 。因为 alist[mid] > item ，故应在前半段中查找。

2、令新的 end=mid-1=2 ，而 front=0 不变，则新的 mid=1 。此时 item > alist[mid] ，故确定应在后半段中查找。

3、令新的 front=mid+1=2 ，而 end=2 不变，则新的 mid=2，此时 alist[mid]=item ，查找成功。

算法如下：

1、确定查找范围front = 0，end = N-1，计算中项mid =（front+end）// 2。

2、若alist[mid] = item或front >= end,则结束查找；否则，向下继续。

3、若alist[mid] < item,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若alist[mid] > item，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。

python实现

def find_value(alist, item):
    front = 0
    end = len(alist) - 1
    find = False

    while front <= end:
        mid = (front + end) // 2
        if item < alist[mid]:
            end = mid - 1
        elif item > alist[mid]:
            front = mid + 1
        else:
            find = True
            break

    return find

if __name__ == '__main__':
    alist = [3, 12, 24, 36, 55, 68, 75, 88]
    print(find_value(alist, 24))

# True