Binary Search - Notes

Binary search is versatile: classic exact-match, lower_bound (first >= target), upper_bound (first > target).

Template (lower_bound):

1
int lower_bound(vector<int>& a, int target){
2
  int l=0, r=a.size();
3
  while(l<r){
4
    int m = l + (r-l)/2;
5
    if(a[m] < target) l = m+1; else r = m;
6
  }
7
  return l; // index of first >= target
8
}

Edge cases: empty array, all elements < target, duplicates — choose variant carefully.