查找就是在集合中寻找特定值的过程，线性查找是查找算法中最简单的算法，下面介绍原理。

线性查找

我们假设有一张写满数字的纸，没有特定的顺序，当要确定数字13是否在这些数字中时，我们会怎么做？我们可能会从头到尾的看这些数字，并将每个数字和13进行比较，当在这个过程中发现13的时候，退出并显示找到了它；如果最后没有发现13，就显示13并不在其中。这个策略就叫做“先行查找”，也就是逐个查找数据项列表，直到找到目标值。简单代码如下：

def search(x,nums):
    for i in range(len(nums)):
        if nums[i]==X: #item found, return the index value
            return i
    return -1   #loop finished, item was not in list

这种方法对于数据量不是很大的列表来说还可以，但对于数据量很大的还有 更好的方法。下面介绍一下二分查找。

二分查找

二分查找的思想也很简单，就像猜数字游戏，选择1~100之间的数字，每次猜测告诉结果是否正确、猜的过高还是过低。我们可以先猜测50，如果数字更高，则可能范围是50~100.下一个猜测逻辑就是75，每次我们猜测剩下数字的中间值，尝试缩小可能的范围。这个策略就是二分查找。二分指的是两个，在每个步骤中，我们将剩余的数字分为两个部分。二分查找适用于查找有序列表。基本思想是用两个变量来跟随数据项列表范围的端点，最初将变量low和high分别设置为列表的第一个和最后一个位置。算法的核心是一个循环，查看剩余范围中间的数据项，将它与x进行比较。如果x小于中间数据项，则移动high，这样就能查找缩小到下半部分；如果x较大，则我们移动low。当找到x或不再有更多的地方（low>high)时ii，循环终止。代码如下：

def search(x,nums):
    low=0
    high=len(nums)-1
    while low<=high:
        mid=(low+high)//2
        item=nums[mid]
        if x==item:
            return mid
        elif x<item:
            high=mid-1
        else:
            low=mid+1
    return -1