C++ 標準庫有序區間查找算法：binary_search、lower_bound、upper_bound

針對已排序區間 [first, last) 的三大查找算法，均為對數級時間。

1. binary_search

bool binary_search(It first, It last, const T& val);

• 返回 val 是否存在；
• 不返回位置，僅判斷存在性。

2. lower_bound

It lower_bound(It first, It last, const T& val);

• 返回首個 ≥ val 的迭代器；
• 若全 < val，返回 last；
• 可視為「保持有序的最左插入位置」。

3. upper_bound

It upper_bound(It first, It last, const T& val);

• 返回首個 > val 的迭代器；
• 若全 ≤ val，返回 last；
• 可視為「保持有序的最右插入位置」。

關鍵性質

• lower_bound == upper_bound ⇔ val 不在區間中；
• [lower_bound, upper_bound) 即為等於 val 的元素範圍（等價於 equal_range）；
• 均要求嚴格弱序（operator< 或自定義比較器）。

示例

vector pets = {"cat","dog","fish","snake","turtle"};
auto lb = lower_bound(pets.begin(), pets.end(), "dog"); // 指向 "dog"
auto ub = upper_bound(pets.begin(), pets.end(), "dog"); // 指向 "fish"
cout << *lb << " " << *ub; // 輸出: dog fish