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.