Python列表查找 顺序查找 二分查找

列表查找：从列表中查找指定元素：

1. 输入：列表、待查找元素
2. 输出：元素下标或为、未查找到元素

顺序查找：

1. 从列表第一个元素开始，顺序进行搜索，直到找到为止

二分查找：

二分查找

假设现在有1-9位数，我想找到3。定义两个变量low和high，low为开始的下标，high为结束的下标。每次取中间的下标mid，就是(low+high)÷2。

 1    2    3    4    5    6    7    8    9
low                mid                  high 
 1    2    3    4    5    6    7    8    9
low  mid       high
              
 1    2    3    4    5    6    7    8    9
          low  high             
          mid

mid下标为5，3在mid左边，没有找到3，接着将high的下标移动到4的位置，即mid-1的位置，再次更新mid=(low+high)÷2的位置，即2的下标，这次3在mid的右边，将low的下标+1，即2位置，再计算mid的值，就找到了3。

按照以上的分析，编写代码,之前先搞一个计时的函数当做装饰器，因为我们后面都会用到：

import time
def cal_time(func):
    def wrapper(*args,**kwargs):
        start_time=time.time()
        x=func(*args,**kwargs)
        end_time=time.time()
        print('time cost:%s,%s'% (func.__name__,str(end_time-start_time)))
        return x
    return wrapper

二分查找代码参考：

@cal_time
def bin_search(data_set,val):
    low=0
    high=len(data_set)-1
    # low=high的时候有一个数
    while low<=high:
        mid=(low+high)//2
        if data_set[mid]==val: # 目标值等于mid
            return mid # 返回下标
        elif data_set[mid]<val: #目标值大于mid，即目标值在mid右边
            low=mid+1
        else:#目标值小于mid，即目标值在mid左边
            high=mid-1
    return
data=list(range(100000)) # 有序列表
bin_search(data,123)