二分查找

基本原理

给定一个排好序的list，假如没排好序，先排序。然后用待查值和列表中间值比大小。若待查值大则说明在右边；否则在左边。

代码

# -*- coding: utf-8 -*-
'''
二分查找：
    给定一个排好序的list，假如没排好序，先排序。
    然后用待查值和列表中间值比大小。若待查值大则说明在右边；否则在左边。
'''
def quick_sort(input_list):

    if len(input_list) <= 1:              # 若长度为1，则直接返回
        return input_list
    left =[]
    right = []
    for i in range(1,len(input_list)):    # 将第一个值作为参照
        if input_list[i] <= input_list[0]:
            left.append(input_list[i])
        else:
            right.append(input_list[i])
    return quick_sort(left) + [input_list[0]] + quick_sort(right)

def binary_search(ilist,value):

    left = 0                             # 设置哨兵
    right = len(ilist) -1

    while right-left > 1:                # 当至少存在三个元素时，查找中间值
        middle = (left + right) // 2
        if value == ilist[middle]:
            return middle
        if value > ilist[middle]:
            left = middle
        if value < ilist[middle]:
            right = middle
    if value == ilist[left]:             # 当只剩下两个元素时，用if判断分别
        return left                      # 判断左右值是否相等。
    if value == ilist[right]:
        return right
    else:
        return -1

if __name__ == '__main__':
    pre_list = [1, 6, 3, 3, 7]
    key = 6
    # 由于pre_list 是无序，所以先排好序。
    ordered_list = quick_sort(pre_list)
    res = binary_search(ordered_list,key)
    print(res)

易忘点和易错点

a. 计算中间值middle是在while循环内部，不是在外面。