App Inventor 2 算法之 - 二分算法（Binary Search）實現(xiàn)，快速查找定位
應(yīng)用介紹
二分算法（Binary Search）是生活中非常常用的折半算法，能解決快速查找、快速定位的問題，主要用到數(shù)學(xué)和邏輯代碼塊。
本示例程序演示了采用普通遍歷的方式和二分的方式分別需要幾次能夠猜中隨機給出的數(shù)字。
二分算法（Binary Search）教程（難度系數(shù)：★★☆）
教程入口：App Inventor 2 中文網(wǎng)（fun123.cn）?-> 登陸 ->?“項目指南”?-> 二分算法（BinarySearch）"開始學(xué)習(xí)"。
App基本邏輯設(shè)計
設(shè)計一個普通遍歷算法，從 1 開始逐個往上猜，這也是最笨的一種方式，當(dāng)然最終能夠猜對，當(dāng)隨機數(shù)是100時，最多需要猜100次。
再設(shè)計一個二分算法，每次猜中間折半的結(jié)果，比如第一次猜50，如果小了則再猜75，如此直到不能再折半為止，也定能猜中。至于需要幾次猜中，大家可以利用本示例程序進行驗證，本教程最后會給出答案。
準(zhǔn)備工作
界面簡單布局，如下：
讓App程序從 1 ~ 100 中隨機生成一個數(shù)字，定義一個空列表，設(shè)置到“列表顯示框”組件中：
普通遍歷算法
普通遍歷方式很簡單，設(shè)計一個 1 ~ 100的循環(huán)，每次比對一下是否和上面的隨機數(shù)相等，相等就是猜中了，就不用繼續(xù)猜了。代碼如下：
二分算法
二分方式代碼如下：
原理示意圖如下：
注意點：計算中間二分?jǐn)?shù)字的時候，需要向下取整，否則計算出來的是小數(shù)，當(dāng)然不是我們想要的，我們的前提是猜整數(shù)數(shù)字。
舉個例子：
App隨機給出的數(shù)字是17，我們依次猜的是：
(1 +100)/2 = 50（大了） 1 50 100
(1 +50)/2 = 25（大了） 1 25 50
(1 +25)/2 = 13（小了） 1 13 25
(13+25)/2 = 19（大了） 13 19 25
(13+19)/2 = 16（小了） 13 16 19
(16+19)/2 = 17（猜中） 16 17 19
開始測試
點擊按鈕開始測試，列表中會顯示兩種方式猜中需要的次數(shù)，二分的話還會輸出每次猜的具體是哪個數(shù)字。
后記
測試下來，我們會發(fā)現(xiàn)，都是7次或7次之內(nèi)就能猜中，其中的原理是什么呢？
算法復(fù)雜度是O(logN)。2^7 = 128 > 100，因此最多7次能猜中。大家可以思考并嘗試一下將100改為1000，這時最多需要幾次猜中？
不僅如此，在計算機科學(xué)中，二分算法（Binary Search）也是非?；A(chǔ)的算法，使用場景非常的多，有序表的檢索、數(shù)據(jù)庫索引技術(shù)等。
