二分查找原理及实现

女爷i 2021-11-16 12:42 296阅读 0赞

假如现在有一组1到100的数，这是一个有序的序列。现在我就从这组数里面选一个数，然后让你猜我选的数，我会告诉你是大了还是小了，最终猜到我选的数。

一种方法是从1开始猜，假如我选的数是100，那么你就要猜100次（实际上我觉得猜到99也就知道选的数是100了，可能是为了确定一下吧）

还有一种二分查找，每次选择中间的数，比如50，无论我说大了还是小了，都可以舍弃一半的数不需要考虑了，就这样不断选取中间的数，直到没有中间数为止，这样就可以猜到我选的数了。

实现：

range函数返回1~101的数组，不包括101.

def binary_search(list, item):
        low = 0
        high = len(list) - 1
        counter = 0
        while low <= high:
            mid = int((low + high) / 2)
            counter += 1
            guess = list[mid]
            print(guess, end=" ")
            if guess == item:
                print("\n总计查找了{}次".format(counter))
                print("查到的下标索引为{}".format(mid))
                return mid
            if guess > item:
                high = mid - 1
            else:
                low = mid + 1
        print("\n请选择数组中的一个数")
        return None
    
    
    listArr = range(1, 101)
    binary_search(listArr, 100)

执行结果为：

50 75 88 94 97 99 100
    总计查找了7次
    查到的下标索引为99

这里也一样我觉得猜到99就知道是哪位数了，无论是大了（98）还是小了（100）还是正好（99）都很清楚。

把代码改了一下：

counter = 0
    
    
    def binary_search(list, item):
        print("需要从数组里找的数是{}".format(item))
        print("开始查找：")
        global counter
        low = 0
        high = len(list) - 1
        if low == high and list[0] == item:
            print("数组里就一位数还用犹豫猜哪个吗？")
            return 0
        while low < high:
            mid = int((low + high) / 2)
            counter += 1
            guess = list[mid]
            print(guess, end=" ")
            if guess > item:
                high = mid - 1
            elif guess < item:
                low = mid + 1
            if low == high:
                return low
            if guess == item:
                return mid
        print("\n请选择一个数组内的值")
        return None
    
    
    listArr = range(1, 101)
    num = binary_search(listArr, 100)
    if num != None:
        print("\n总共查了{}次".format(counter))
        print("查到的下标索引为{}".format(num))

执行结果：

需要从数组里找的数是100
    开始查找：
    50 75 88 94 97 99
    总共查了6次
    查到的下标索引为99

返回的结果都是下标索引99。