前言：

在猜數字遊戲中，出題者會先想一個介於 1 ~ 100 的數字，接著你必須猜出對方心裡所想的數字是多少。
如果猜錯，對方會提示「要比 OO 大一點」或者「要比 OO 小一點」以讓你繼續猜，能夠猜越少次越好。

直覺地，一個好的的猜數字策略會由中間值開始猜，
也就是先猜可能的範圍 1 ~ 100 的中間值 50 。

假設對方回答：「要比 50 大一點」，則可能的範圍變為 51 ~ 100，
因此第二次改猜 51 ~ 100 的中間值 75 。

假設對方回答：「要比 75 小一點」，則可能的範圍變為 51 ~ 74，
因此第三次改猜 51 ~ 74 的中間值 62，以此類推 。

這類策略我們稱為「二分搜尋法(Binary Search)」，
也就是紀錄當下可能範圍，並在過程中盡可能縮小它，以加快搜尋速度。

以上面例子來說，最糟的情況會由一開始 100 個可能數字，對半砍為 50 個、25 個、13 個、7 個、4 個、2 個、1 個，
也就是對於 100 個可能數字，至多猜七次(log₂100 ≈ 6.64)必定可以得到最後答案。
當然，如果幸運的話，也可能只猜一次就得到答案。

除了猜數字遊戲，二分搜尋法(Binary Search)也應用在其他許多地方。

題目敘述：

在遊戲中玩家可以自由加入公會組成同盟，
已知現在有一個公會由 N 個成員組成( 1 ≤ N ≤ 500,000 )，
N 個成員的玩家編號由小到大分別為 x₀, x₁, ..., x_N-1 ( 1 ≤ x_i ≤ 1,000,000,000 )。

現在有 Q 個玩家( 1 ≤ Q ≤ 1,000,000,000 )，
請利用二分搜尋法快速確認，這 Q 個玩家是否是公會成員。

解題概念：

舉例來說，某公會有 N = 10 個成員，
成員的玩家編號由小到大分別為 3, 9, 12, 14, 15, 20, 24, 25, 32, 36。

假設想要確認玩家編號 20 是否是公會成員，我們可以先初始搜尋範圍(左邊界 = 0, 右邊界 = N-1 = 9)：

第一次搜尋(左邊界 = 0, 右邊界 = 9, 中間值 = (0+9)/2 = 4)
3, 9, 12, 14, [[15]], 20, 24, 25, 32, 36
因 15 < 20，如果 20 存在的話，應在搜尋範圍的右半邊，因此調整搜尋範圍的左邊界為中間值右邊一格，即 4+1 = 5。

第二次搜尋(左邊界 = 5, 右邊界 = 9, 中間值 = (5+9)/2 = 7)
3, 9, 12, 14, 15, 20, 24, [[25]], 32, 36
因 25 > 20，如果 20 存在的話，應在搜尋範圍的左半邊，因此調整搜尋範圍的右邊界為中間值左邊一格，即 7-1 = 6。

第三次搜尋(左邊界 = 5, 右邊界 = 6, 中間值 = (5+6)/2 = 5)
3, 9, 12, 14, 15, [[20]], 24, 25, 32, 36
因 20 = 20，可知該玩家是公會成員。

假設想要確認玩家編號 18 是否是公會成員，我們可以先初始搜尋範圍(左邊界 = 0, 右邊界 = N-1 = 9)：

第一次搜尋(左邊界 = 0, 右邊界 = 9, 中間值 = (0+9)/2 = 4)
3, 9, 12, 14, [[15]], 20, 24, 25, 32, 36
因 15 < 18，如果 18 存在的話，應在搜尋範圍的右半邊，因此調整搜尋範圍的左邊界為中間值右邊一格，即 4+1 = 5。

第二次搜尋(左邊界 = 5, 右邊界 = 9, 中間值 = (5+9)/2 = 7)
3, 9, 12, 14, 15, 20, 24, [[25]], 32, 36
因 25 > 18，如果 18 存在的話，應在搜尋範圍的左半邊，因此調整搜尋範圍的右邊界為中間值左邊一格，即 7-1 = 6。

第三次搜尋(左邊界 = 5, 右邊界 = 6, 中間值 = (5+6)/2 = 5)
3, 9, 12, 14, 15, [[20]], 24, 25, 32, 36
因 20 > 18，如果 18 存在的話，應在搜尋範圍的左半邊，因此調整搜尋範圍的右邊界為中間值左邊一格，即 5-1 = 4。

此時因為左邊界 > 右邊界(左邊界 = 5, 右邊界 = 4)，已不是合法的搜尋範圍，可知該玩家不是公會成員。