有序數組中數字出現次數：二分法查找首尾位置

問題

在已排序數組中統計指定數字出現次數。如 [1,2,3,4,4,4,4,6,8,9] 中 4 出現 4 次。

二分法改進

分別查找目標數的最左位置和最右位置。二分查找時，遇到相等值：
• 找最左 → 繼續在左半區間搜索 (right = mid-1)
• 找最右 → 繼續在右半區間搜索 (left = mid+1)
最後次數 = rightPos - leftPos + 1。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

int findBound(const vector& a, int target, bool leftmost) {
    int l = 0, r = (int)a.size() - 1, pos = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (a[mid] < target) l = mid + 1;
        else if (a[mid] > target) r = mid - 1;
        else {
            pos = mid;
            if (leftmost) r = mid - 1;
            else l = mid + 1;
        }
    }
    return pos;
}

int main() {
    vector a = {1,2,3,4,4,4,4,6,8,9};
    int target = 4;
    int left = findBound(a, target, true);
    int right = findBound(a, target, false);
    if (left == -1) cout << "Not found\n";
    else cout << "Count of " << target << ": " << right - left + 1 << endl;
    return 0;
}

複雜度

O(log n) 時間，O(1) 空間。比線性掃描快得多，適合大數據量。