min
在 Python 中 min 函数可以直接返回列表中的最小项。
现在用代码演示一下，怎么用代码实现在列表中检索一个最小项。
def fn(L):
MinIndex = 0
CurrentInder = 1
while CurrentInder < len(L):
if L[MinIndex] > L[CurrentInder]:
MinIndex = CurrentInder
CurrentInder += 1
return L[MinIndex]
L = [21,45,2,3,5,2,57,6,4]
print(fn(L))
解释一下
先把列表的第一项，也就是索引为0的值置为最小项，然后跟第二项，也就是索引为1的值进行比较，设置while循环，退出条件是列表的每一项都比较完。这样遍历了整个列表，最小项的索引也就找到了。
那最大项的索引岂不是改个条件就获取了，没错。试一下吧。
in
在python 中 in 的运算符用于在列表中搜索一个特定的项，这个列表没有要求。那这个in方法用代码实现起来就比较简单了。
def fn(L,target):
position = 0
while position < len(L):
if L[position] == target:
return ('索引是：{}，值是：{}'.format(position,L[position]))
position +=1
return -1
L = [21,45,1,3,5,2,57,6,4]
print(fn(L,4))
只要挨个比较目标值就完事了。假如目标值不在列表中返回 -1 好了
但要考虑一件事，顺序搜索列表的性能怎么样呢？
- 在最好的情况下，目标值正好在列表的前面，算法只进行了一次迭代就找到了目标值，复杂度为O(1)。
- 最坏的情况下，目标项在列表的最末尾或者不在列表里，我们要比较n次（假如列表长度为n），那么最坏情况下，顺序搜索的复杂度为O(n)。
- 再来考虑一下平均情况下的算法复杂度。要确定平均情况下，把在每一个可能的位置找到目标项所需的迭代次数相加，总和除以n，这样一算，算法执行了（n+n-1+n-2+ ++1）/2 或者 （n+1）/ 2 次迭代。对于很大的n ，常数因子2的作用不大，因此，平均情况下的复杂度仍然为O（n）.
得出结论，顺序搜索最好情况的性能很少见，而平均情况和最坏情况的性能则基本相同。
对于没有按照任何顺序排列的数据，顺序搜索是必要的，当列表有序的时候，可以使用二叉搜索，又称二分查找。
二分查找
假设列表中的项都是按照升序排列的，二分查找就是先找到中间一项跟目标项进行比较，如果相等就返回该项的位置，也就是索引。否则，如果目标项比列表中间项大，就在中间项以后的位置查找，如果目标项比列表中间项小，就在中间项以前的位置查找。
def fn(L,target):
left = 0
right = len(L) - 1
while left <= right:
mid = (left + right) // 2
if target == L[mid]:
return mid
elif target > L[mid]:
left = mid + 1
else:
right = mid - 1
return -1
L = [1,2,3,4,5,6,7,8,9]
print(fn(L,9))
首先设置 while 循环的退出条件是：查找的目标项跟列表中的中间项相等。
为了实现这个退出条件，我们一分为二这个列表，看看目标项在列表前后的哪个部分，当第一遍循环之后我们缩小一半的查找区域，再次循环又缩小一半。直到匹配出目标项。
对于大小为 n 的列表，实际上执行了 n/2/2/2/2/ 的连续除法，直到结果为1，假设 k 是用 n 除以 2 的次数。要求解k,让 n/2^k=1 就行了，那么 n=2^k，k=㏒₂n ,因此二分查找的复杂度为 O(k=㏒₂n)。
结语
最近会放上一些算法的文章，来锻炼算法能力。毕竟最底层的东西才是最实用的。
网友评论