百家號不支持代碼格式，文章裡的代碼排版都是亂的。
如果需要拷貝代碼，可以去同名的微信公眾號。
接上題在一個列表中查找符合條件的元素，需要遍歷整個列表，逐個元素檢查。
上一篇介紹過，遍歷列表有2種方式。
import random
a = random.sample(range(1,100),80)
for x in a:
if 88 == x:
print("列表裡有88")
break
else:
print("列表裡沒有88")
import random
a = random.sample(range(1,100),80)
for i in range(0,len(a)):
if 88 == a[i]:
print("第%d個元素是88"%(i+1))
break
else:
print("列表裡沒有88")
第一種方式看上去更簡單，但一般情況下，我們不僅需要找到這個元素，還需要知道元素在列表中的位置，所以，反而第二種方式用得更多。
無處不在的查找
查找恐怕是這個世界上每天發生得最多的事情了。尤其是在網際網路上。
我們每天
在百度上查找資料
在淘寶、京東上查找商品
在QQ音樂、網易音樂上查找歌曲
在晉江查找小說
……
但可能我們都沒有思考過一個問題，電腦是如何從數以億計的海量數據裡找到我們想要？我們試著用一個簡單的例子來說明海量數據的查找其實是一件很有技術含量的事情。
比如說辦理護照，窗口的工作人員要你提供身份證號碼，然後在電腦上輸入你的身份證號碼，查找核實你的資料。
我們假設，全國所有人的身份證號碼都保存在一個列表裡。那麼這個列表就有13億多個元素。按照我們文章開頭介紹的方法，每次查找都需要遍歷整個列表，最差的情況就需要找13億次。
我們知道電腦的速度很快，1秒鐘甚至可以找1000萬次。
可是 13億/1000萬 = 130秒 ，需要 2 分多鐘。
真的需要這麼長時間嗎？有沒有更快的辦法？
神奇的「二分查找」
假設下面的列表，一共有13億個數字
最小是3，最大是100億。
數字從小到大排列，但沒有規律。
需要在裡面查找數字 x = 314159260
需要從第一個元素依次往後查找嗎？
顯然不需要。因為數字有序！
拿x和列表中間的元素比較，如果相等，就找到了。
如果 x 比中間元素大，顯然，我們只需要在中間元素右邊裡繼續查找。
反之亦然。
這樣，每次都可以把查找的範圍縮小一半。
這就是「二分查找」
最多需要查找多少次呢？
其實就是求 n 除以多少次2之後等於1。
也就是數學上以2為底的對數函數：log2(n)
math模塊提供了以2為底的對數函數 log2()。
也就是說最壞的情況，也只需要31次，就能完成！
和13億次相比，簡直是天壤之別。
這就是「二分查找」的神奇之處。
Python實現「二分查找」
我們先生成一個從0到1億的數列。
注意：range()函數返回的並不是列表類的實例，但是是可以被循環的數列，所以滿足我們的需求。
l1 = range(0,100000000)
然後我們去查找一個不可能存在的數字， x = 100000001。
當然，你沒有上帝視角，並不知道這個數字不存在。
所以在學會「二分查找」之前，只能逐一查找。
我們再介紹一個新的模塊 datetime. 它有函數可以返回程序執行時的時間。
在for循環查找之前，和查找結束後。
我們分別用 print(datetime.datetime.now())列印出當時的時間。
然後2個時間相減就是查找用的時間。
我們發現，要完成1億次查找，電腦用了將近 16 秒鐘！
和人相比，已經非常非常快了。
但如果是十億，甚至百億、千億的數據，這個速度就太慢，太慢了！
如果用「二分查找」呢？
準備查找
列表的最左邊位置 left = 0
最右邊位置 right = len(l1) - 1
中間位置 mid = (left+right) // 2
開始查找
x 和 中間位置的元素做比較， if x == l1[mid]
如果相等，break 結束。
如果 x 更大，下次只需要查找 mid 右邊的元素，也就是 left = mid +1
反之 right = mid - 1
使用「二分查找」，只用了 0.0006 秒不到！
選擇排序
現實生活中，數據往往是無序的。而我們又時時刻刻都在查找。
所以，想辦法將無序的數據變得有序，從而可以使用「二分查找」就變得非常重要！
給定一個如下的無序列表，如何對它進行排序呢？
import random
list1 = random.sample(range(0,100),9)
問題看上去很簡單。
先找到最小的，放到第1位
再找到次小的，放到第2位
……
這種排序方法被稱為「選擇排序」。
雖然選擇排序看上去很容易理解，並且網上還有無數的解釋教程，甚至還做了像下面這樣形象生動的gif動畫。
但初學者依然很難寫出正確的程序。一個重要的原因是不能真正理解電腦的工作方式。
如果有條件的話，可以找9個盒子，裝入9個不同的數字紙片。
上一篇介紹過，這種方式非常接近列表在電腦裡的真實狀態。
然後實際動手模擬選擇排序的過程，這種方式將非常有助於理解電腦的工作方式，理解選擇排序的程序代碼。
下一篇，我們將詳細介紹這個過程，及對應的程序。
在模擬過程中，要注意的是：
只有拉開盒子，才能看到盒子裡的數字。並且去拉另一個盒子前，要把當前盒子重新關上。不能挪動盒子，只能把盒子裡的數字紙片拿出來交換位置。