python 二分查找的实现

二分查找基于有序的元素列表；对于包含n个元素的列表，最多需要log2N步，简单查找最多需要N步：

    1. 如果查找的列表是无序的要先进行排序 如:sorted([])

    2. 根据要查找的数据进行索引定位

    3.递归更新列表与索引

实例：

#利用二分查找法在0 - 99 查找77
sorted_list = [i for i in range(100)]
end_number = 77

def FindNumber(sorted_list):
    list_lg = len(sorted_list)
    center_index = int(list_lg/2)
    center_num = sorted_list[center_index]
    if center_num < end_number:
        sorted_list = sorted_list[center_index:]
    elif center_num > end_number:
        sorted_list = sorted_list[0:center_index]
    else:
        return center_num
    FindNumber(sorted_list)

FindNumber(sorted_list)

 

排序算法中快速排序的实现（与二分查找有异曲同工之妙），大O的运行时间为 O(n * log n)：

    1. 找到一个基准值

    2. 需要排序的列表分为两个子数组：小于基准值的元素数组，大于基准值的元素数组

    3. 递归进行第二步 

实例：

import random

unsort_list = [random.randint(0, 1000) for i in range(100)]

def QuitSort(unsort_list):
    if len(unsort_list) < 2:
        return unsort_list
    else:
        choice_num = unsort_list[0]
        less_list = [item for item in unsort_list[1:] if item <= choice_num]
        greater_list = [item for item in unsort_list[1:] if item > choice_num]

        return QuitSort(less_list) + [choice_num] + QuitSort(greater_list)

QuitSort(unsort_list)