演算法中階・二分搜尋找邊界
二分搜尋不只找值:找左右邊界、對答案二分、在環狀資料找跳回點。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
排序日誌中某日的範圍
中等二分搜尋一份日誌已依日期(yyyymmdd 整數)由小到大排序,同一天會有很多筆。補跑某一天的資料時,要先找出這一天在日誌裡的第一筆與最後一筆位置。
輸入:
第 1 行:日誌每筆的日期,以空白分隔(已排序,可重複)
第 2 行:查詢數 q
接下來 q 行:每行一個要查的日期
輸出:q 行,每行
第一筆位置 最後一筆位置(位置從 0 起算);日誌裡沒有這一天印-1 -1。要求:自己寫二分搜尋(不用 bisect 模組,也不要逐筆掃):分別找「第一個 ≥ 該日期」與「第一個 > 該日期」的位置。
範例輸入:
20240101 20240102 20240102 20240104
2
20240102
20240103
範例輸出:
1 2
-1 -1
類型對應:LeetCode「Find First and Last Position of Element in Sorted Array」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
最低處理速率
中等二分搜尋一個 worker 要在 H 小時內處理完 n 個分區。worker 的速率是每小時 k 萬筆(k 是正整數),而且每個小時只能處理一個分區:某個分區剩不到 k 萬筆時,那個小時處理完它就閒著,不會接著處理下一個分區。所以處理一個 p 萬筆的分區要花 ⌈p / k⌉ 小時。
請找出能在 H 小時內(含)處理完全部分區的最小 k。題目保證 H ≥ n。
輸入:
第 1 行:H
第 2 行:每個分區的資料量(萬筆,正整數,以空白分隔)
輸出:兩行
第 1 行:最小的 k
第 2 行:用這個 k 實際需要的小時數
要求:對 k 做二分搜尋(k 越大越快處理完,可行與不可行在某個值之後分界),不要從 1 一個一個試。
範例輸入:
8
3 6 7 11
範例輸出:
4
8
類型對應:LeetCode「Koko Eating Bananas」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 03
環狀日誌找最舊紀錄
中等二分搜尋設備用固定大小的環狀緩衝區存日誌:寫滿後從頭覆蓋,所以把緩衝區從頭讀到尾,會看到一段遞增的時間戳,接著可能「跳回」較小的時間戳再繼續遞增(也可能完全沒有跳回)。時間戳彼此不同。請找出最舊(最小)的時間戳在緩衝區的位置。
輸入:一行,緩衝區從頭到尾的時間戳(整數,以空白分隔,至少一筆)
輸出:兩行
第 1 行:最舊時間戳的位置(從 0 起算)
第 2 行:最舊的時間戳
要求:用二分搜尋,比較中間值和最後一個值決定往哪一半找,不要用 min() 或逐筆掃。
範例輸入:
40 50 60 10 20 30
範例輸出:
3
10
類型對應:LeetCode「Find Minimum in Rotated Sorted Array」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了