Embedded Files
在說明二元(分)搜尋前，先介紹循序搜尋，二元搜尋演算法效率較高但需要事先排序，循序搜尋資料不需要排序，兩種演算法各有優缺點。
循序搜尋
找出成績陣列中是否包含成績為59分的學生，找到第一個學生成績為59分為止。
舉例說明
(1) 第一個學生的成績(60) 是否為59分，若是則輸出「找到59分的學生」程式結束。
(2) 否則比較第二個學生的成績(90)是否為59分，若是則輸出「找到59分的學生」程式結束。
(3)否則比較第三個學生的成績(44)是否為59分，若是則輸出「找到59分的學生」程式結束。
(4)否則比較第四個學生的成績(98)是否為59分，若是則輸出「找到59分的學生」程式結束。
(5)否則比較第五個學生的成績(50)是否為59分，若是則輸出「找到59分的學生」程式結束。
(6)若全部都找不到成績59分的學生，則輸出「找不到59分的學生」
解題想法
想要找出班上第一次段考成績是否有59分的學生，可能需要有全班成績單，從頭開始依序找，(1)第一個學生成績是否為59分，若是則輸出「找到59分的學生」程式結束，(2)否則比較第二個學生的成績是否為59分，若是則輸出「找到59分的學生」程式結束，(3)依此類推，直到比較到最後一個學生的成績為止，(4)若全部都找不到成績59分的學生，則輸出「找不到59分的學生」。
循序搜尋程式碼
程式碼效率
第5到11行要掃描成績陣列的每一個元素，所以程式碼效率為O(n)
二元搜尋(Binary Search)
搜尋前需要將資料進行排序才能使用二元搜尋。二元搜尋除了用於搜尋資料外，有時候也可以用於找出最佳解，例如：分配物品的最佳解，將n個大小不同的長方形蛋糕，分給m個人，不能將不同蛋糕的剩餘部分組合起來分給一個人，蛋糕若太小可以不分配，每個人都要獲得相同大小的蛋糕，每個人獲得的蛋糕大小可以是浮點數，此時需要使用二元搜尋加快逼近要分配的大小。
二元搜尋是對已排序資料進行尋找某筆資料是否存在，平均而言，二元搜尋比循序搜尋找到該資料的執行時間要短，也就是有較好的執行效率。使用「已排序成績陣列中是否包含成績為59分的學生」為例，進行二元搜尋概念的說明。 從頭到尾依序找尋稱作「循序搜尋」，但對已經由小到大排序好的資料可以使用「二分搜尋」方式加快找尋速度，因為已經排序可以從中間開始找，若要找的元素比中間元素值大，則往右邊找，若要找的元素比中間元素值小，則往左邊找，依此類推直到找到為止。
使用二元搜尋搜尋值
假設已排序的11個學生的成績陣列，如下圖，以二分搜尋方式找尋成績為59分的學生。
Step1) 取第一個到第11個學生成績中間的那位學生，第六個學生的成績(78) 是否為59分，若是則輸出「找到59分的學生」程式結束。
Step2)因為59分小於78分，往左邊由第一到第五個學生成績中間的那位學生，第三個學生的成績(62)是否為59分，若是則輸出「找到59分的學生」程式結束。
Step3)因為59分小於62分，往左邊由第一到第二個學生成績中間的那位學生，第一個學生的成績(45)是否為59分，若是則輸出「找到59分的學生」程式結束。
Step4)因為59分大於45分，往右邊判斷第二個學生的成績(59)是否為59分，找到59分的學生，輸出「找到59分的學生」程式結束。
輸入說明
本題不需要輸入。
輸出說明
輸出是否找到成績為59分。
輸入範例
無
輸出範例
mid更新為5
檢查score[5]=78是否等於59
left更新為0, right更新為4
mid更新為2
檢查score[2]=62是否等於59
left更新為0, right更新為1
mid更新為0
檢查score[0]=45是否等於59
left更新為1, right更新為1
mid更新為1
檢查score[1]=59是否等於59
陣列第2個元素等於59分
解題想法
這樣的演算法需要一個成績陣列，事先將成績陣列由小到大排序好，一個迴圈(while)用於檢查陣列範圍內是否還有元素，迴圈內檢查「目前成績」是否等於59分，若找到一個成績等於59分，則輸出「找到59分的學生」，否則若「目前成績」大於59分，59分可能在「目前成績」為左半部，「目前成績」為左半部陣列元素取位於中間元素的成績，若「目前成績」小於59分，59分可能在「目前成績」為右半部，「目前成績」為右半部成績陣列取位於中間元素的成績。若找不到可以比較的「目前成績」，則輸出「找不到59分的學生」。
程式碼
程式碼效率
第6到20行為二分搜尋，每次根據數值的大小可以排除一半的可能性，所以程式碼效率為O(log(n))就可以找到，二分搜尋較循序搜尋效率要好，缺點為二分搜尋需事先排序。
跳躍式搜尋(Jump Search)
已排序資料也可以使用跳躍式搜尋，其演算法效率比二分搜尋差，但優於循序搜尋，每次跳躍n^0.5長度，長度為n的資料，總共n^0.5次一定可以搜尋完畢，最後再循序搜尋長度n^0.5範圍內的資料，最多需要執行n^0.5次，演算法效率為O(n^0.5)，比二分搜尋的演算法效率O(log(n))差，比循序搜尋的演算法效率O(n)好。優點程式碼較二分搜尋簡單，不需要分左右兩半。
程式碼效率
第5到19行為跳躍式搜尋，每次可以跳過n^0.5個元素，最多n^0.5次可以搜尋n個元素，所以程式碼效率為O(n^0.5)就可以找到。
(2-3)整數平均分配
有n包不同口味的糖果要分給m個小朋友，每包糖果的個數不同，每個小朋友只接受同一口味的糖果，小朋友只在乎個數是否一樣，可以任意給同一口味的糖果，若某包糖果個數較多，就可以分給多個小朋友，多出的可以不分配，某包個數過少的糖果，導致不能分配出去，求每個小朋友最多可以拿幾顆糖果。
輸入說明
輸入n表示會輸入n包不同口味的糖果，接著輸入n行，每一行一個數字，表示該包糖果的個數，接著輸入m，表示有幾個小朋友，保證m<=n，且n<1000。
輸出說明
每個小朋友最多可以拿幾顆糖果。
輸入範例
10
10
21
16
40
55
45
35
54
33
46
10
輸出範例
22
解題想法
本範例使用二分搜尋，不斷測試各種糖果顆數的分配是否足夠分給m個小朋友，使用二分搜尋不斷逼近解答，比循序搜尋逼近解答快。需要撰寫一個函式，可以不斷輸入糖果顆數，檢查是否可以分給m個小朋友，如果可以回傳true，否則回傳false，二分搜尋不斷依據此函式所回傳的結果，修正糖果顆數左邊界與右邊屆逼近正確答案。
程式碼
STL內建二分搜尋
資料排序後才能使用二分搜尋，STL內建的二分搜尋為函式lower_bound、upper_bound與binary_search，舉例如下。
以下函式的搜尋範圍為v.begin()到v.end()，搜尋的範圍包含最左邊的元素v.begin()，但不包含最右邊的元素v.end()，v.end()是最後一個元素的下一個元素，稱作左閉右開。
it = lower_bound(v.begin(), v.end(), x)，搜尋範圍v.begin()到v.end()，第一個大於等於x的元素，回傳迭代器(iterator)到it，it減去v.begin()就會是符合條件元素的索引值，找不到回傳v.end()，最後一個元素的下一個元素，該元素不存在。
it = upper_bound(v.begin(), v.end(), x)，搜尋範圍v.begin()到v.end()，第一個大於x的元素，回傳迭代器(iterator)到it，it減去v.begin()就會是符合條件元素的索引值，找不到回傳v.end()，最後一個元素的下一個元素，該元素不存在。
result = binary_search(v.begin(), v.end(), x)，搜尋範圍v.begin()到v.end()，x是否存在，回傳布林值到result，如果找到x，則回傳true，否則回傳false。
執行結果
lower_bound位置4
upper_bound位置8
是否存在1
範例練習1 APCS10603第4題基地台
上傳作業：http://203.68.236.9/problem/b0029
zerojudge題目網址：https://zerojudge.tw/ShowProblem?problemid=c575
出處APCS
問題描述
為因應資訊化與數位化的發展趨勢，某市長想要在城市的一些服務點上提供無線網路服務，因此他委託電信公司架設無線基地台。某電信公司負責其中 N 個服務點，這 N個服務點位在一條筆直的大道上，它們的位置(座標)係以與該大道一端的距離 P[i]來表示，其中 i=0~N-1。由於設備訂製與維護的因素，每個基地台的服務範圍必須都一樣，當基地台架設後，與此基地台距離不超過 R (稱為基地台的半徑)的服務點都可以使用無線網路服務，也就是說每一個基地台可以服務的範圍是 D=2R(稱為基地台的直徑)。現在電信公司想要計算，如果要架設 K 個基地台，那麼基地台的最小直徑是多少才能使每個服務點都可以得到服務。
基地台架設的地點不一定要在服務點上，最佳的架設地點也不唯一，但本題只需要求最小直徑即可。以下是一個 N=5 的例子，五個服務點的座標分別是 1、2、5、7、8。
0 1 2 3 4 5 6 7 8 9
▲ ▲ ▲ ▲ ▲
假設 K=1，最小的直徑是 7，基地台架設在座標 4.5 的位置，所有點與基地台的距離都在半徑 3.5 以內。假設 K=2，最小的直徑是 3，一個基地台服務座標 1 與 2 的點，另一個基地台服務另外三點。在 K=3 時，直徑只要 1 就足夠了。
輸入說明
輸入有兩行。第一行是兩個正整數 N 與 K，以一個空白間格。第二行 N 個非負整數P[0],P[1],....,P[N-1]表示 N 個服務點的位置，這些位置彼此之間以一個空白間格。請注意，這 N 個位置並不保證相異也未經過排序。本題中，K<N 且所有座標是整數，因此，所求最小直徑必然是不小於 1 的整數。
輸出說明
輸出最小直徑，不要有任何多餘的字或空白並以換行結尾。
範例輸入
5 2
5 1 2 8 7
5 1
7 5 1 2 8
範例輸出
3
7
範例練習2 uva 1152 - 4 Values whose Sum is 0
上傳作業：http://203.68.236.9/problem/b0030
UVa出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3593
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c,d ) A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
1
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Sample Output
5
解題策略
a[]與b[]相加後每個數儲存到ab[]，排序ab[]
將每一個(-c[]-d[])的值到ab[]中找尋該值的lower_bound與upper_bound，upper_bound減去lower_bound就是該值在ab[]的個數
lower_bound(ab,ab+len,k)找到大於等於k的由左到右第一個遇到的元素的指標
upper_bound(ab,ab+len,k)找到大於k的由左到右第一個遇到的元素的指標
範例練習3 APCS202007 第3題圓環出口
zerojudge題目：https://zerojudge.tw/ShowProblem?problemid=f581
有 n 個房間排成一個環，編號分別是 0 到 n−1。 房間之間有單向的路徑，編號 i 的房間可以走到編號 (i+1)modn的房間。 每次進入編號 i 的房間可以獲得 pi 個點數（最一開始待的房間也可以獲得點數）。
現在依序有 m 個任務，第 i 個任務需要蒐集到 qi 個點數。對於每次的任務，若一開始在編號 s 的房間，且走到編號 t 的房間時候可以蒐集到需要的點數，則完成這次任務後會停在編號 (t+1)modn 的房間。
一開始在編號 0 的房間，依據接收到 m 個任務，請求出完成第 m 個任務後會停在哪個編號的房間？
輸入說明
第一行包含兩個正整數 n,m(1≤n≤200000,1≤m≤20000)。 第二行包含 n 個正整數 p0,p1,p2,…,pn−1，p 的總和不超過 10^9。 第三行包含 m 個正整數 q0,q1,q2,…,qm−1， qi 不會超過 p 的總和。
配分
20分: 1≤n,m≤100
80分: 同原題目限制。
輸出說明
輸出一個非負整數表示最後停在哪個編號的房間
輸入範例1
7 3
2 1 5 4 3 5 3
8 9 12
輸出範例1
4
第一次需要8點，2+1+5，停留在編號3的房間，第二次需要9點，4+3+5，停留在編號6的房間，第三次需要12點，3+2+1+5+4，停留在編號4的房間，答案為4
輸入範例2
4 3
1 3 5 7
4 2 2
輸出範例2
0
解題策略
前綴和、二分搜
範例輸入 #1
5 1
0 2 1 3 4
2 3 5 4 6
範例輸出 #1
2
範例輸入 #3
2 1
1 2
2 3
範例輸出 #3
1
範例輸入 #2
8 2
3 1 4 3 7 2 2 5
5 3 7 4 8 7 4 6
範例輸出 #2
5
解題策略：排序+multiset+二分搜尋(lower_bound)
活動依照結束時間由小到大排序，若結束時間相同，可以不用依照開始時間排序。機器結束時間依序加入multiset會形成平衡的binary search tree，使用二分搜尋lower_bound找出第一個iterator(it)大於等於新活動的開始時間，(--it)就會找到最後一個小於活動開始時間的機器，該機器執行新活動，更新結束時間到multiset。
輸入說明
輸出說明
輸出雷射光共反射幾次。
輸入範例
10
2 0 1
2 -1 1
7 -1 0
7 2 1
4 2 0
4 1 0
3 1 1
3 2 0
1 -1 1
1 4 0
4
2 1 0
5 -3 1
4 2 1
6 -2 0
輸出範例
9
0
範例測資一見題目敘述內的圖表。
範例測資二可以發現沒有任何 y=0的鏡子，因此反射次數為0 。
解題策略 模擬與二分搜尋
模擬，使用adjacency list紀錄相同x可以到達的y到X[]，接著由小到大排序X[]內的y，使用adjacency list紀錄相同y可以到達的x到Y[]，接著由小到大排序Y[]內的x。使用二分搜尋加快速度，本範例二分搜尋可以使用upper_bound找出大於x的第一個元素，lower_bound找出大於等於x的第一個元素。
從(0,0)向東出發找到第一個y=0，x>0的第一個鏡子，使用upper_bound找出x大於的第一個元素。若該鏡子為\，則往南，否則往北。若往南，表示在相同x，使用lower_bound找到第一個y大於等於0的點，該元素指標減1(找到小於0的第一個元素)，表示找到y小於0的第一個鏡子為反射鏡子。若該鏡子為\，則往東，否則往西。依次類推找出所有反射鏡子的個數。
範例練習6 APCS202201 第3題數位占卜
zerojudge網址 https://zerojudge.tw/ShowProblem?problemid=h083
占卜籤筒有m支籤，每一支籤為一個由英文小寫字母組成的字串。從籤筒內抽出兩支籤，若將這兩支籤上的字串S和T連接起來形成的字串可以將該字串拆成左右兩半並且內容一樣，則抽到聖筊代表神明同意，否則神明不同意或是沒回答。
例如抽出的兩支籤上的字串分別為 piep 和 ie，則相連接起來的字串為 piepie 可以拆分左右兩半為相同的字串 pie 和 pie，但抽出的兩支籤為 foo 和 bar 時則不滿足條件。
神奇的是，若抽到的兩支籤S和T為聖筊，則不管是將T接在S後面或是順序反過來接起來，都可以是聖筊，再次說明了這兩支籤有著某種神秘力量在祝福著抽到的幸運人。例如 piep 和 ie 不管是使用 piepie 或是 iepiep 都可以拆分成兩個一樣的字串。
詢問籤筒內這m支籤，有幾個 pair 可以形成聖筊。相同的兩支籤組合計算一次即可。
輸入說明
輸入一個正整數m，接下來有m的字串，每個字串長度最長為100。
數字範圍
(1)1<=m<=50000
(2)籤筒內所有字串均相異
輸出說明
輸出一個正整數，代表有幾個 pair 滿足條件。
輸入範例
3
a
aba
aaa
5
abyyyab
y
yy
yyy
yyyy
輸出範例
1
3
提示 ：
範例 1
總共有 1 組，為 {aaa, a}
範例 2
總共有 3 組，分別為 {abyyyab, yyy}, {yyy, y}, {yyyy, yy}
解題策略 字串分割、排序、二元搜尋
找出首尾一樣的字串，例如：abyyyab的ab，只要找出yyy是否出現過，接著使用二元搜尋(binary_search)確定yyy是否出現過，檢查每個字串為O(n)，字串如果首尾相同則需要二元搜尋找出字串是否存在需要O(log(n))，排序字串需要O(n*log(n))，當n遠大於字串長度時，字串長度可以忽略，整體演算法效率為O(n*log(n))
範例練習7 APCS202201 第4題牆上海報
zerojudge網址 https://zerojudge.tw/ShowProblem?problemid=h084
有一個由n個木板所組成的柵欄，每個木板的高度為h[1],h[2],...,h[n] ，有 k張海報要張貼在柵欄上，每張海報的寬度為w[1],w[2],...,w[k]並且高度均為1。
若要張貼海報在高度為x的高度，則第i 張海報需要張貼在一個寬度為w[i]的連續並且高度都不小於x的木板上，且每張海報張貼的高度需要一致、按照順序並不能重疊 (可以相連)。詢問最高可以貼到多高的位置。
輸入說明
第一行有兩個正整數n,k，接下來一行有 n個正整數代表每個木板的高度，最後一行有k個正整數代表每張海報的寬度。
數字範圍
1 <= n <=200000
1<=k<=5000
1<=h[i]<=10^9
w[1]+w[2]+..+w[k]<=n
輸出說明
輸入最大可以張貼的高度
輸入範例
5 1
6 3 7 5 1
3
10 3
5 3 7 5 1 7 5 3 8 4
2 2 1
輸出範例
3
5
解題策略：二分搜尋
自訂函式iswork，高度為x，能否將所有海報貼上，可以則回傳true，否則回傳false。使用二分搜尋先從柱子最高(R)與最低(L)取一半到變數(M)，呼叫函式iswork以M為輸入進行判斷，若此高度M可以貼上，將最低(L)設定為M，否則最高(R)設定為M-1，再取最高(R)與最低(L)取一半到變數(M)，繼續呼叫iswork以M為輸入進行判斷。
範例練習8 APCS202210第4題蓋步道
zerojudge網址：https://zerojudge.tw/ShowProblem?problemid=j125
有一個大小為 n×n 的方形區域，hij 代表位於座標 (i,j) 的格子該處的海拔高度。 工程團隊想要從該區域的左上角 (1,1) 鋪設一條步道到右下角 (n,n)，鋪設的步道可以視為在該區域內上下左右四個方向從左上角走到右下角的一條路徑。
考量到行人在步道上行走的安全，必須要注意步道的高低落差，並希望可以建立出一個最大高度差最小的步道鋪設方案。 請輸出該鋪設方案最大高度差的最小值和在該最大高度差的前提下步道的最短路徑長度。
輸入說明
第一行為一個數字 n(1≤n≤300)，代表該區域的大小。 接下來有 n 行，第 i 行有 n 個正整數，每一個正整數 hij(1≤hij≤10^6) 代表該位置的海拔高度。
子題配分
(20%): n≤10，高度不超過 10
(20%): n≤300，高度不超過 10^3
(60%): n≤300，高度不超過 10^6
輸出說明
輸出兩行，第一行輸出鋪設方案中最大高度差的最小值，第二行輸出在該最大高度差下從左上走到右下的最短路徑長度。
輸入範例
4
9 4 3 2
5 9 8 10
3 3 2 8
6 3 3 4
輸出範例
4
6
解題策略
二元搜尋+BFS
找出路徑上最大高度差，但(0,0)到(n,n)所有可能路徑取最小
使用BFS確認是否可以找到一條路徑從(0,0)到(n,n)其高度差小於等於m
利用二元搜尋逼近m
step[y][x]用於紀錄點(x,y)幾步可以到達，設定step[0][0]為0，
step[y][x]等於-1表示還未走到，過程中曾經走過(step[y][x]>-1)就不再BFS，
ｍ值縮小時，如果轉彎會得到更小的差值，路徑就會轉彎
Page updated
Google Sites
Report abuse