AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・中階・3 題

演算法中階・二分搜尋找邊界

二分搜尋不只找值:找左右邊界、對答案二分、在環狀資料找跳回點。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 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 執行,只用標準函式庫。

    作答登入後可作答
  2. 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 執行,只用標準函式庫。

    作答登入後可作答
  3. 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 執行,只用標準函式庫。

    作答登入後可作答