f679: 公會成員
Tags : Binary Search 二分搜
Accepted rate : 65人/81人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-22 22:53

Content

前言:

在猜數字遊戲中,出題者會先想一個介於 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 個可能數字,至多猜七次(log2100 ≈ 6.64)必定可以得到最後答案。
當然,如果幸運的話,也可能只猜一次就得到答案。

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

題目敘述:

在遊戲中玩家可以自由加入公會組成同盟,
已知現在有一個公會由 N 個成員組成( 1 ≤ N ≤ 500,000 ),
N 個成員的玩家編號由小到大分別為 x0, x1, ..., xN-1 ( 1 ≤ xi ≤ 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),已不是合法的搜尋範圍,可知該玩家不是公會成員。

Input

第一行有兩個正整數 N 和 Q,代表公會人數和詢問次數
( 1 ≤ N ≤ 500,000,  1 ≤ Q ≤ 1000,000,000)

第二行由左至右有 N 個相異正整數 x,
代表公會成員的玩家編號( 1 ≤ x ≤ 1000,000,000 )
兩兩之間以空格隔開,並且必定由小至大

最後有 Q 行,
每行有一個正整數 T,代表想要確認的玩家編號
( 1 ≤ T ≤ 1000,000,000 )

Output

輸出共有 Q 行,
若欲確認的玩家在公會中,則輸出"Yes"
反之,輸出"No"

Sample Input #1
10 2
3 9 12 14 15 20 24 25 32 36
20
18
Sample Output #1
Yes
No
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (25%): 5.0s , <1K
公開 測資點#1 (25%): 5.0s , <10M
公開 測資點#2 (25%): 5.0s , <10M
公開 測資點#3 (25%): 5.0s , <10M
Hint :
Tags:
Binary Search 二分搜
出處:
教學題 [管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」