Binary Search 中的 lower bound & upper bound

前言

c++ 的 STL 有提供兩個跟 binary seach 有關的 function: lower_bound 和 upper_bound, 每次在寫 leetcode 相關的題目時都會一直忘記這兩個 function 的定義，故決定紀錄一下兩者的定義及用法

Include STL

lower_bound 和 upper_bound 被定義在 <algorithm> 裡面

#include <algorithm>

Lower Bound

找出數列中第一個 大於或等於 target 的位置, 換句話說就是找到 >= target 的最小值的位置

// vector<int> v;
// assume v is a sorted array
auto it = lower_bound(v.begin(), v.end(), target);
int idx = it - v.begin();

Upper Bound

找出數列中第一個 大於 target 的位置, 換句話說就是找到 > target 的最小值的位置

// vector<int> v;
// assume v is a sorted array
auto it = upper_bound(v.begin(), v.end(), target) - v.begin();
int idx = it - v.begin();

lower_bound 和 upper_bound 都會回傳 對應型態的 iterator, 如果傳入的 sequence 找不到目標值，就會回傳 v.end()