(递归)二分查找算法python

条件

• 查找的数据源必须是有序的.

原理分析

• 取数据的中间数和要查找的目标进行对比,然后确立最大(小)值,再算出中间数,再和查找目标对比,如此反复直到中间数和查找目标相等为止。

循环二分查找

list_box = [x for x in range(1, 100)]


def find_target_num(list1, target_num):
    """
    :type list1: list[int]
    :type target_num : int
    """
    low = 0
    high = len(list1) - 1
    while high >= low:
        mid = int((low + high) / 2)
        mid_value = list1[mid]
        if target_num == mid_value:
            return mid
        if target_num > mid_value:
            low = mid + 1
        else:
            high = mid - 1
    return None


print(find_target_num(list_box, 25))

递归二分查找法

listbox = [2,4,5,6,7,8]
def recursion_search(listone, low, high, num):
    mid = (low + high) // 2
    if low > high:
        return None
    if num > listone[mid]:
        return recursion_search(listone, mid + 1, high, num)
    elif num < listone[mid]:
        return recursion_search(listone, low, mid - 1, num)
    else:
        return mid
print(recursion_search(listbox, 0, len(listbox)-1, 8))# 5