二分查找

上一小节说的线性查找针对的是无序序列,假如一个序列已经有序了呢,我们还需要从头找到尾吗?当然不用,折半(二分)是一种经典思想。日常生活中还有哪些经典的二分思想呢?

  • 猜数字游戏
  • 有些民间股神,告诉一堆人某个股票会涨,告诉另一半人会跌。后来真涨了,慢慢又告诉信了他的一半人另一个股票会涨,另一半说会跌。就这样韭菜多了总有一些人信奉他为股神…...

举例:

def binary_search(sorted_array, val):
    if not sorted_array:
        return -1

    beg = 0
    end = len(sorted_array) - 1

    while beg <= end:
        mid = int((beg + end) / 2)  # beg + (end-beg)/2, 为了屏蔽 python 2/3 差异我用了强转
        if sorted_array[mid] == val:
            return mid
        elif sorted_array[mid] > val:
            end = mid - 1
        else:
            beg = mid + 1
    return -1


def test_binary_search():
    a = list(range(10))

powered by Bornforthi.comFile Modify: 2021-09-17 15:06:45

results matching ""

    No results matching ""