线性查找与二分查找入门

线性查找

def linear_search(data_set,value):
    for i in range(len(data_set)):
        if data_set[i]==value:
            return i
    return
print(linear_search([11,22,33,44,55,66],44))

线性查找，时间复杂度O(n)

二分查找

从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半

def binary_search(li,val):
    low=0
    high=len(li)-1
    while low <= high:
        mid=(low+high)//2
        if li[mid]>val:
            high=mid-1
        elif li[mid]<val:
            low=mid+1
        else:
            return mid
    else:
        return None
li=list(range(1000))
print(binary_search(li,305))

二分查找，循环减半的过程，时间复杂度O(logn)

总结

• 二分查找虽然快,但是需要提前排好序,相当于一部分工作提前做了

参考

一看就懂-图解二分查找和线性查找 - 简书
https://www.jianshu.com/p/e5c6ea36869a