ZeroJudge 解題筆記：d732. 二分搜尋法

作者：王一哲
日期：2025年9月13日


ZeroJudge 題目連結：d732. 二分搜尋法

解題想法

可以自訂二分搜尋法的函式，也可以用 Python 的 bisect.bisect_left 或是 C++ algorithm 函式庫的 lower_bound 解題。注意，這題的位數是從 1 開始計算，搜尋到的索引值要加 1 才是答案。

Python 程式碼

自己寫二分搜尋法，使用時間約為 1.1 s，記憶體約為 20.9 MB，通過測試。

def binary_search(arr, target):  # 自己寫二分搜尋法，代入串列 arr 及目標 target
    low, high = 0, len(arr)-1  # 索引值的下限、上限
    while low <= high:  # 如果 low 小於等於 high 繼續執行
        mid = (high - low) // 2 + low  # 計算中間值 mid
        if arr[mid] == target: return mid+1  # 找到目標，回傳 mid，離開函式
        if arr[mid] > target:  # 目標在左半邊，降低 high
            high = mid - 1
        else:  # 目標在右半邊，提升 low
            low = mid + 1
    if arr[low] != target: return 0  # 如果沒有找到目標，回傳 0

if __name__ == "__main__":
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    for t in map(int, input().split()):
        print(binary_search(arr, t))

bisect_left，使用時間約為 0.3 s，記憶體約為 20.9 MB，通過測試。

from bisect import bisect_left

n, k = map(int, input().split())
arr = list(map(int, input().split()))
for x in map(int, input().split()):
    idx = bisect_left(arr, x)
    if arr[idx] == x: print(idx+1)
    else: print(0)

C++ 程式碼

自己寫二分搜尋法，使用時間約為 45 ms，記憶體約為 440 kB，通過測試。

#include <cstdio>
using namespace std;

int binary_search(int* arr, int n, int t) {
    int low = 0, high = n-1;
    while(low <= high) {
        int mid = (high - low) / 2 + low;
        if (arr[mid] == t) return mid + 1;
        if (arr[mid] > t) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int arr[n];
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    for(int i=0; i<k; i++) {
        int x; scanf("%d", &x);
        printf("%d\n", binary_search(arr, n, x));
    }
    return 0;
}

lower_bound，使用時間約為 45 ms，記憶體約為 676 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k; scanf("%d %d", &n, &k);
    vector<int> arr (n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    for(int i=0; i<k; i++) {
        int x; scanf("%d", &x);
        auto it = lower_bound(arr.begin(), arr.end(), x);
        if (*it == x) printf("%ld\n", it - arr.begin() + 1);
        else printf("0\n");
    }
    return 0;
}