猜數(shù)字
現(xiàn)有兩個(gè)玩家，分別為玩家A和玩家B；
玩家A從一個(gè)范圍中選擇一個(gè)數(shù)（例如從 [1,1000] 中選擇了352）
讓玩家B猜玩家A選擇的數(shù)
若玩家B猜的數(shù)字x小于352，說(shuō)明x<352<=1000,應(yīng)當(dāng)在 [x+1,1000]中繼續(xù)猜；
若玩家B猜的數(shù)字x大于352，說(shuō)明1<=352<x,應(yīng)當(dāng)在 [1,x-1] 中繼續(xù)猜。
顯然，每次選擇當(dāng)前范圍的中間數(shù)去猜，就能盡可能快的逼近正確的數(shù)字，并最終將其猜出來(lái)。
由此，引申出的經(jīng)典問(wèn)題：如何在一個(gè)嚴(yán)格遞增序列A中找出給定的數(shù)x。
最直接的辦法是：線性掃描序列中的所有元素
如果當(dāng)前元素恰好為x，則表明查找成功；
-
如果掃描完整個(gè)序列都沒有發(fā)現(xiàn)給定的數(shù)x,則表明查找失敗，說(shuō)明序列中不存在數(shù)x。
順序查找的時(shí)間復(fù)雜為O(n)(其中n為序列元素個(gè)數(shù))，
二分查找是基于有序序列的查找算法，該算法一開始令 [left,right]為整個(gè)序列的下標(biāo)區(qū)間，然后每次測(cè)試當(dāng)前 [left,right]的中間位置 mid = (left+right)/2, 判斷 A[mid]與與查詢的元素x的大小。
-
如果 A[mid]==x,說(shuō)明查找成功，退出查詢。
image-20210419215233629.png
- 如果 A[mid]>x,說(shuō)明元素x在mid位置的左邊，因此往左子區(qū)間[left,mid-1]繼續(xù)查找。
- 如果 A[mid]<x,說(shuō)明元素x在mid位置的右邊，因此往右子區(qū)間 [mid+1,right]繼續(xù)查找。
二分查找：每一步都可以去除當(dāng)前區(qū)間的一半元素，因此其時(shí)間復(fù)雜度是O(logn)。
