python二分查找的原理

"""

应用前提：在一个含有n个元素的有序序列中定位目标值 时间复杂度：O(logn)

该算法维持两个参数low和high,这样可使所有候选条目的索引位于low和high之间。首先, low=0和high=n-1。然后我们比较目标值和中间值候选项，即索引项[mid]的数据。

mid =L(low + high)/2 ]考虑以下三种情况:

- 如果目标值等于[mid]的数据, 然后找到正在寻找的值，则查找成功并且终止。

- 如果目标值< [mid] 的数据, 对前半部分序列重复这一过程，即索引的范围从low到mid-1.

- 如果目标值> [mid] 的数据，对后半部分序列重复这一过程，即索的范围从mid+1到high。

- 如果low >high,说明索引范围[low， high]为空,则查找不成功。该算法被称为二分查找

"""

def binary_search(alist, item):

    """非递归"""

    first = 0

    last = len(alist) - 1

    found = False

    while first <= last and not found:

        mid = (first + last) // 2

        if alist[mid] == item:

            found = True

        else:

            if item < alist[mid]:

                last = mid - 1

            else:

                first = mid + 1

    return found

def binary_search_recursion(alist, item):

    if len(alist) > 0:

        mid = len(alist) // 2

        if alist[mid] == item:

            return True

        elif item < alist[mid]:

            return binary_search_recursion(alist[:mid], item)

        else:

            return binary_search_recursion(alist[mid + 1:], item)

    return False

if __name__ == '__main__':

    ret = binary_search_recursion([17, 20, 26, 31, 44, 54, 55, 65, 77, 69], 26)

    print(ret)

    ret = binary_search([17, 20, 26, 31, 44, 54, 55, 65, 77, 69], 68)

    print(ret)