Python中实现二分查找的两种方法

我大概收集了两种写法，分别是循环和递归两个方式

二分查找：搜索一般是从列表的中间开始查找，如果中间刚好是目标值，则搜索结束，返回结果；如果目标值大于中间值，则按这个中间值分割列表，在大于中间值的这部分列表里继续查找；如果目标值小于中间值，则按这个中间值分割列表，在小于中间值的这部分列表里继续查找。

这里需要注意的是如果想要使用二分查找，前提需要先将列表排序，这样才能实现；（排序算法在后尾贴出了）

二分查找

lst = [10389, 60076, 61238, 61266, 64305, 64317, 65705, 66507, 73590, 75721]
target = 64317

def binary_search1(lst, target):
    """二分查找 —— 循环版"""
    n = len(lst)
    first = 0
    last = n-1
    while first <= last:
        mid = (first + last) // 2  # 必须整除
        if lst[mid] == target:
            return True
        # 如果中间值大于目标值，则查找lst[mid]的前部分，把last为mid-1
        elif lst[mid] > target:
            last = mid - 1
        # 如果中间值小于目标值，则查找lst[mid]的后部分，把first为mid-1
        else:
            first = mid + 1
    return False

def binary_search2(lst, target):
    """二分查找 —— 递归版"""
    n = len(lst)
    if n > 0:
        mid = n // 2  # 列表长度的中间作下标
        if lst[mid] == target:
            return True  # 查找成功
        # 如果中间值大于目标值，则截取列表的前半部分继续查找
        elif lst[mid] > target:
            return binary_search2(lst[:mid], target)
        # 如果中间值小于目标值，则截取列表的后半部分继续查找
        else:
            return binary_search2(lst[mid+1:], target)
    else:
        return False  # 查找失败

if __name__=='__main__':
    
    # print(binary_search1(lst, target))
    print(binary_search2(lst, target))

快速排序

def quick_sort(lst, i, j):
    if i >= j:
        return lst
    pivot = lst[i]
    low = i
    high = j
    while i < j:
        while i < j and lst[j] >= pivot:
            j -= 1
        lst[i], lst[j] = lst[j], lst[i]

        while i < j and lst[i] <=pivot:
            i += 1
        lst[i], lst[j] = lst[j], lst[i]

    quick_sort(lst, low, i-1)
    quick_sort(lst, i+1, high)

    return lst

if __name__=='__main__':
    lst = [23,1,4,56,22,45,78,100,13,55]
    res_lst = quick_sort(lst,0,len(lst)-1)
    print(res_lst)