① 搜索最小值
python的min函数返回列表中的最小项
1 def indexOfMin(lyst): 2 minIndex = 0 3 currentIndex = 1 4 while currentIndex < len(lyst): 5 if lyst[currentIndex] < lyst[minIndex]: 6 minIndex = currentIndex 7 currentIndex += 1 8 return minIndex
算法复杂度为O(n)
② 顺序搜索一个列表
python的in运算符作为list类中名为__contains__的一个方法实现的。
1 def sequentialSearch(target,lyst): 2 position = 0 3 while postion < len(position): 4 if target == lyst[position]: 5 return position 6 position += 1 7 return -1
最好情况、最坏情况和平均情况的性能
顺序搜索的分析要考虑如下三种情况：
1.在最坏的情况下，目标位与列表的末尾，或者根本不在列表内，那么算法必须访问每一个项，并对大小为n的列表执行n次迭代，因此顺序搜索的最坏的复杂度为O(n)
2.在最好的情况下，算法只进行了1次迭代就在第一个位置找到目标项，复杂度为O(1)
3.要确认平均情况，把每个可能的位置找到目标项所需的迭代次数相加，并用总和除以n，因此算法执行了（n+1）/2次的迭代，对于很大的n来说，常数因子2的作用并不大，因此平均情况的复杂度仍然为O(n)
③ 有序列表的二叉搜索
1 def binarySearch(target,sortedLyst): 2 left = 0 3 right = len(sortedLyst) - 1 4 while left <= right: 5 middle = (left + right)//2 6 if target == sortedLyst[middle]: 7 return middle 8 elif target < sortedLyst[middle]: 9 right = middle - 1 10 else: 11 left = middle + 1 12 return -1
二叉搜索的最坏情况的复杂度为O(log2n)
二叉搜索可能比顺序搜索要更为高效，然而选择何种搜索算法取决于列表中的数据组织方式
④ 比较数据项
二叉搜索的搜索最小项，都是假设列表中的项是可以相互比较的，在python中这意味着这些项具有相同的数据类型，并且它们都识别比较运算符==，<和>。几个内建的python类型的对象，例如数字、字符串和列表，都可以用这些运算符来进行比较
为了允许算法对一个新对象的类使用比较运算符，应该在该类中定义__eq__,__lt__和__gt__方法。__lt__方法：
def __lt__(self,other):
如果self小于other，该方法返回True，否则返回False。
1 class SavingAccount(object): 2 def __init__(self,name,pin,balance=0.0): 3 self._name = name 4 self._pin = pin 5 self._balance = balance 6 7 def __lt__(self,other): 8 return self._name < other._name 9 10 11 s1 = SavingAccount('Ken',"1000",0) 12 s2 = SavingAccount('Bill',"1001",30) 13 print(s1<s2) #False 14 print(s1>s2) #True 15 print(s1==s2) #False 16 17 s3 = s1 18 print(s3==s1) #True
当字符串应用<运算符的时候，python自动运行__lt__方法，就像在调用str函数运行__str__方法一样
总结：
1.搜索最小项算法必须访问列表的每一个数，除非列表已经排序，因此算法总是线性的，因此最好的情况，最坏的情况和平均的情况的性能都是O(n)
2.顺序搜索最好的情况性能是O(1)，最坏的情况是O(n)，平均情况（1+2+...+n）/n或2/n，因此平均情况下算法的性能是O(n)