簡易搜尋法（Sequential Search）& 二元搜尋法（Binary search）

相信大家一定有玩過猜數字的遊戲，或是他更常見出現的名字『終極密碼』

為了避免有人沒玩過，還是簡單介紹一下，這個遊戲就是出題者從 1 -100 之間選擇一個數字，猜題者來猜數字，出題者會依據猜題者給的數字告訴他目前的範圍在哪裡，一直到被某個猜題者猜中為止。

例如：出題者選了一個數字 37

A 玩家：46
出題者：1 到 46
B 玩家：33
出題者：33 到 46
C 玩家： 37
出題者：到了！

所以我們要怎麼猜呢？

可以從頭開始一個一個猜

A 玩家：1
出題者：1 到 100
B 玩家：2
出題者：2 到 100
…

這其實就是簡易搜尋法！

簡易搜尋法（Sequential Search）- Big O(n)

因為他是一個從頭開始一個一個檢查的搜尋法，所以最差的情況下，執行時間會是 Big O(n)，就像如果出題者出 100，你從頭開始猜，就要從 1 猜到 100，是一個滿慢的演算法。

因此要加快找到的速度，除了隨便猜之外，我們很常見的做法是『剖半』。

出題者選： 36
A 玩家：50
出題者：1 到 50
B 玩家：25
出題者：25 到 50
C 玩家：37
出題者：25 到 37
A 玩家：31
出題者：31 到 37
B 玩家：34
出題者：34 到 37
C 玩家：35
出題者：35 到 37
A 玩家：36
出題者：中了

從中間的數字猜，每次都可以排除一半的數字

這就是二元搜尋法

二元搜尋法（Binary search）- Big O(log n)

在這個演算法裡，最差的情況下，執行時間是 Big O(log n)，log2 100 = 6.64… 所以最多猜 7 次就一定會猜中，明顯比簡易搜尋法快得多。

在生活中有很多很像二元搜尋法的場景，例如翻字典，當我們想要找一個 I 開頭的字，我們會從中間打開字典，看目前翻到的單字是在 I 的前面還後面，然後繼續重複這個動作，直到找到要的字。

不過二元搜尋法的限制是，搜尋的內容必須先被排序好，像這邊的 1~100 就是有先被排好的。

也因為他是連續性的資料，所以我們在 JavaScript 裡會用到 array，在 Python 裡則會使用 list 來放資料。

範例：給一串排列好的數字 1, 3, 5, 7, 9，猜一個數字看他在第幾個，若找不到這個數字則回傳 None（JavaScript 回傳 null）。

Python 的寫法如下：

JavaScript 的寫法如下：

語法補充

在 Python 裡面基本的加減乘除跟 JavaScript 是一樣的，但平方會寫成 **

>>> 3 ** 2 
9

除法也有分別

當使用 / 時，表示 floating-point division，也就是浮點數的除法
>>> 5 / 2
2.5
當使用 // 時，表示 floor division，會無條件捨去
>>> 5 // 2
2