min
在 Python 中 min 函數(shù)可以直接返回列表中的最小項。
現(xiàn)在用代碼演示一下，怎么用代碼實現(xiàn)在列表中檢索一個最小項。
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的值進行比較，設(shè)置while循環(huán)，退出條件是列表的每一項都比較完。這樣遍歷了整個列表，最小項的索引也就找到了。
那最大項的索引豈不是改個條件就獲取了，沒錯。試一下吧。
in
在python 中 in 的運算符用于在列表中搜索一個特定的項，這個列表沒有要求。那這個in方法用代碼實現(xiàn)起來就比較簡單了。
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))
只要挨個比較目標(biāo)值就完事了。假如目標(biāo)值不在列表中返回 -1 好了
但要考慮一件事，順序搜索列表的性能怎么樣呢？
- 在最好的情況下，目標(biāo)值正好在列表的前面，算法只進行了一次迭代就找到了目標(biāo)值，復(fù)雜度為O(1)。
- 最壞的情況下，目標(biāo)項在列表的最末尾或者不在列表里，我們要比較n次（假如列表長度為n），那么最壞情況下，順序搜索的復(fù)雜度為O(n)。
- 再來考慮一下平均情況下的算法復(fù)雜度。要確定平均情況下，把在每一個可能的位置找到目標(biāo)項所需的迭代次數(shù)相加，總和除以n，這樣一算，算法執(zhí)行了（n+n-1+n-2+ ++1）/2 或者 （n+1）/ 2 次迭代。對于很大的n ，常數(shù)因子2的作用不大，因此，平均情況下的復(fù)雜度仍然為O（n）.
得出結(jié)論，順序搜索最好情況的性能很少見，而平均情況和最壞情況的性能則基本相同。
對于沒有按照任何順序排列的數(shù)據(jù)，順序搜索是必要的，當(dāng)列表有序的時候，可以使用二叉搜索，又稱二分查找。
二分查找
假設(shè)列表中的項都是按照升序排列的，二分查找就是先找到中間一項跟目標(biāo)項進行比較，如果相等就返回該項的位置，也就是索引。否則，如果目標(biāo)項比列表中間項大，就在中間項以后的位置查找，如果目標(biāo)項比列表中間項小，就在中間項以前的位置查找。
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))
首先設(shè)置 while 循環(huán)的退出條件是：查找的目標(biāo)項跟列表中的中間項相等。
為了實現(xiàn)這個退出條件，我們一分為二這個列表，看看目標(biāo)項在列表前后的哪個部分，當(dāng)?shù)谝槐檠h(huán)之后我們縮小一半的查找區(qū)域，再次循環(huán)又縮小一半。直到匹配出目標(biāo)項。
對于大小為 n 的列表，實際上執(zhí)行了 n/2/2/2/2/ 的連續(xù)除法，直到結(jié)果為1，假設(shè) k 是用 n 除以 2 的次數(shù)。要求解k,讓 n/2^k=1 就行了，那么 n=2^k，k=㏒?n ,因此二分查找的復(fù)雜度為 O(k=㏒?n)。
結(jié)語
最近會放上一些算法的文章，來鍛煉算法能力。畢竟最底層的東西才是最實用的。
