搜索算法

搜索最小值

python的min函数返回列表中的最小的项。为了研究这个算法，我们可以实现一个自定义函数作为替代。如下所示：

def indexOfMin(lyst):
    '''
    返回列表中最小的项的索引
    '''
    minIndex = 0
    currentIndex = 1
    while currentIndex < len(lyst):
        if lyst[currentIndex] < lyst[minIndex]:
            minIndex = currentIndex
        currtentIndex += 1
    return minIndex

从上述函数中可以看出，循环外有三条指令执行相同的次数，即minIndex、currentIndex及return minIndex执行次数和数据规模没有直接关系。循环内的三条指令if语句、minIndex = currentIndex和currentIndex += 1这三个指令在执行时，会随着数据规模的增长而产生线性变化，对于大小为n的列表，必须进行n-1次比较，则说明次算法的复杂度为O(n)。

顺序搜索一个列表

在python中,in运算符作为list类中名为__contains__的一个方法而实现。该方法在列表中搜索一个特定的项。在一个任意排序的列表中，搜索一个目标项的唯一方法是：从第一个位置的项开始，将其与目标相进行比较，如果这两个项相同，则返回True。否则，移动到下一个位置，并且将其项与目标项进行比较。如果该方法到达了最后一个位置，且没有找到目标项，则返回False。这种搜索叫做顺序搜索或者线性搜索。

def sequentialSearch(target, lyst):
    '''
    返回目标项，如果没有目标项则返回-1
    '''
    position = 0
    while position < len(lyst):
        if target == lyst[position]:
            return position
        position += 1
    return -1

最好情况、最坏情况和平均情况的性能

对于顺序搜索算法，在查找一个目标项的时候，在列表开头处做的工作比在列表结尾处做的工作要少。对于这种情况，我们可以确定其最好性能、最坏性能及平均性能。一般而言，我们考虑一个算法的时候，更多的需要考虑其平均性能及最坏性能。顺序搜索算法需要考虑如下情况：

在最坏情况下，目标项位于列表的末尾，或者根本不在列表中，这时候，算法必须访问每一项，并且对列表中的每一项进行迭代，这时候，算的复杂度为O(n)；
在最好的情况下，迭代一次就可以在列表中查询到目标项，此时福再度为O(1);
平均情况下，我们将每一次可能的迭代次数相加，然后除以总次数，即可以得出结论。因此结果是(n + n-1 + n-2 + ... + 1)/n，即(n+1)/2，一般而言，常因数忽略不计，可以看出，平均情况下，算法复杂度仍然为O(n)。

有序列表的二叉搜索

对于没有按照任何顺序进行排序的数据，顺序搜索是必要的，但是对于排序的数据，可以使用二叉搜索(二分查找)。实现代码(假设列表中的元素都是升序)：

def binarySearch(target, sortedList):
    left = 0
    right = len(sortedList) - 1
    while left < right:
        midpoint = (left+right) // 2
        if target == sortedList[midpoint]:
            return midpoint
        elif target < sortedList[midpoint]:
            right = midpoint - 1
        else:
            left = midpoint + 1
    return -1

对于二叉搜索来说，最好的情况就是一次搜索获得结果，最坏的结果可以如下得出，对于大小为n的列表，可以分解为2^k^=n，其中k为搜索使用的次数，得出k=log2n，即二叉搜索的算法复杂度为O(log2n)。