【数据结构和算法】搜索算法

① 搜索最小值

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)