数据结构学习 | 查找

简单查找

• 概述：每次都要遍历序列找到匹配值
• 时间复杂度：O(n)
• 代码：此处略

二分查找

• 概述：给定有序的列表，设定两个基准low和high，分别对应要查找序列的第一个元素和最后一个元素的index。每次匹配index值为（low+high）/2的元素与要寻找的元素
• 时间复杂度：O(logn)
• 代码：

def binary_search(arr,item):
    low=0
    high=len(arr)-1
    while low<=high:
        mid=int((low+high)/2)
        guess=arr[mid]
        if guess<item:
            low=mid+1
        if guess>item:
            high=mid-1
        if guess==item:
            return mid
        else:
           return 0