1. description

Binary search the target in a sorted array or a solution for a monotonic problem.

C++ lowerbound and upperbound assume the array to be sorted in non-decreasing order.

Usually when doing binary search, you need to following the order of array. For example, if the array is in increasing order, we usually find the one that is greater than sth. It’s not possible to use binary search to find the one that is smaller than sth.

So it does not make sense when you perform lowerbound(arr.begin(), arr.end(), target) on an increasing array, which means find the first element that is >= target in an decreasing order array, which violate the searching order.

The lower_bound(arr.begin(), arr.end(), target, greater<int>()) in desendign order array, is used to find the first element <= target. upperbound is used to find the first element < target.

2. usage

2.1. asending ordered array

2.1.1. first greater or equal (lower bound)

lowerbound(nums.begin(), nums.end(), target); Three ways to write lower bound No matter how we represent the binary search window like in [left, right], [left, right) or (left, right). The core idea is shrink the window until the window is empty. (We checked all the elements if the window is empty). This is important to control the while loop condition.

2.1.1.1. [left, right], both side are closed
int search(vector<int>& nums, int target) {
  // [left, right] contains one possible answer, or no answer
  int left = 0, right = nums.size()-1;
  // when left -- right, [left, right] there is one element left, still need to check
  while(left <= right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] < target) {
      left = mid + 1; // invariant: those from [0, left-1] are marked as red ==> not valid answer
    }
    else {
      right = mid - 1; // invariant: those from [right+1, end] are marked as blue ==> valid answer
    }
  }

  // after the loop, left must be in the right of right
  // we can return left of right + 1
  return left;
}
2.1.1.2. [left, right), left side is closed while right side is open
int search(vector<int>& nums, int target) {
  int left = 0, right = nums.size();

  // if left == right, [left, right) there is no elements in the window, we processed all the elements and do not need to check
  while(left < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] < target) {
      left = mid + 1;    // [0, left-1] is those <
    }
    else {
      right = mid;       // [right, end] are those >=
    }
  }

  // after the loop, left will be the same as right, which has the answer
  // return left or right
  return right;
}
2.1.1.3. (left, right), noth side are open
int search(vector<int>& nums, int target) {
  int left = -1, right = nums.size();

  // when left+1 == right (left, right), there is no elements in the window, do not need to check
  while(left+1 < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] < target) {
      left = mid; // [0, left] are invalid
    }
    else {
      right = mid; // [right, end..] are valid
    }
  }

  // after the loop left+1 == right, we processed all the elements
  return right;
}

2.1.2. first greater (upper bound)

upperbound(nums.begin(), nums.end(), target)

2.1.2.1. [left, right]
int search(vector<int>& nums, int target) {
  int left = 0, right = nums.size()-1;
  while(left<=right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] <= target) { // <= will be ignored
      left = mid + 1; // [0, left-1] are marked as red
    }
    else {
      right = mid - 1; // [right+1, ..] are marked as blue
    }
  }

  // left is in the right of right pointer
  // left and right+1 are valid answer, return either one is ok
  return left;
}
2.1.2.2. [left, right)
int search(vector<int>& nums, int target) {
  int left = 0, right = nums.size();
  while(left < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] <= target) {
      left = mid + 1; // [0, left-1] are invalid
    }
    else {
      right = mid; // [right ... end] are valid
    }
  }
  // now left == right, we can return either of these
  return left;
}
2.1.2.3. (left, right)
int search(vector<int>& nums, int target) {
  int left = -1, right = nums.size();
  while(left+1 < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] <= target) {
      left = mid; // [0, left] are invalid
    }
    else {
      right = mid; // [right .. ] are valid
    }
  }
  // now left+1 == right, return left+1 and right are ok
  return right;
}

2.1.3. last smaller or equal

upperbound(nums.begin(), nums.end(), target) - 1

2.1.3.1. [left, right]
int search(vector<int>& nums, int target) {
  int left = 0, right = nums.size()-1;
  while(left <= right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] > target) {
      right = mid - 1; // [right+1 ... end] are invalid
    }
    else {
      left = mid + 1; // [0...left-1] are valid
    }
  }

  // now left is in the right of right
  // return left-1 or right is valid, return any is ok
  return right;
}
2.1.3.2. [left, right)
int search(vector<int>& nums, int target) {
  int left = 0, right = nums.size();
  while(left < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] > target) {
      right = mid; // [right,...] are invalid
    }
    else {
      left = mid + 1; // [0 ... left-1] are valid
    }
  }

  // now left is in the right of left == right
  // left-1 and right-1 are valid, return either is ok
  return left - 1;
}
2.1.3.3. (left, right)
int search(vector<int>& nums, int target) {
  int left = -1, right = nums.size();
  while(left+1 < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] > target) {
      right = mid; // [right end] are invalid
    }
    else {
      left = mid; // [0..left] are valid
    }
  }

  // now left+1 == right
  // left and right - 1 are valid, return anyone is ok
  return left;
}

2.1.4. last smaller

lowerbound(nums.begin(), nums.end(), target) - 1

2.1.4.1. [left, right]
int search(vector<int>& nums, int target) {
  int left = 0, right = nums.size()-1;
  while(left<=right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] >= target) {
      right = mid - 1; // [right+1 .. ] are invalid
    }
    else {
      left = mid + 1; // [0 ... left-1] are valid
    }
  }

  // now left is in the right of left
  // left -1 and right are valid, we can return either
  return right;
}
2.1.4.2. [left, right)
int search(vector<int>& nums, int target) {
  int left = 0, right = nums.size();
  while(left < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] >= target) {
      right = mid;     // [right ... ] are invalid
    }
    else {
      left = mid + 1;  // [0 .. left-1] are valid
    }
  }

  // now left == right
  // left - 1 or right - 1 are valid
  return left - 1;
}

(left, right) 

int search(vector<int>& nums, int target) {
  int left = -1, right = nums.size();
  while(left+1 < right) {
    int mid = left + (right - left) / 2;
    if(nums[mid] >= target) {
      right = mid;  // [right ... ] are invalid
    }
    else {
      left = mid;  // [0...left] are valid
    }
  }

  // now left+1 = right
  // left and right - 1 are valid, return any is ok
  return left;
}

2.1.5. first smaller (does not make sense to use binary search)

2.1.6. first smaller or equal (does not make sense to use binary search)

2.2. desending ordered array

for desending order, we need to overwrite the comparator operator

2.2.1. first smaller or equal (lower bound)

lowerbound(nums.begin(), nums.end(), target, greater<int>())

2.2.2. first smaller (upper bound)

upperbound(nums.begin(), nums.end(), target, greater<int>())

2.2.3. last greater or eqaul

upperbound(nums.begin(), nums.end(), greater<int>()) - 1

2.2.4. last greater

lowerbound(nums.begin(), nums.end(), greater<int>)

2.2.5. first greater (does not make sense to use binary search)

2.2.6. first greater or equal (does not make sense to use binary search)

2.3. paramatric search

Parametric Search is a technique where you use binary search to find the smallest or largest value (parameter) that satisfies a given condition — even when the value itself isn’t in a list or array. For example, you want find the largest value k that can be used to finish something. You can one helper function isok(k), which returns true if k can be used to finish that thing

(left, right) 

int search() {
  int left = -1 (or other impossible value), right = INT_MAX (or other impossible value);
  while(left+1 < right) {
    int mid = left + (left - right) / 2;
    if(!is_ok(mid)) {
      right = mid;  // [right ... ] are invalid
    }
    else {
      left = mid // [0.. left] are valid
    }
  }

  // now left+1 == right
  // left and right - 1 is valid, return either is ok
  return left;
}