二分查找的不完全总结

gistfile1.txt

/*
 * 1. right = nums.size()
 * 2. left < right
 * 3. right = mid
 * 4. return right
 */

int find(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; // [1, 2, 3, 4, 5] 排除 1 2 3 left = 4
    else
      right = mid;
  }

  return -1;
}

int low_bound(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;
    else
      right = mid; // [0, 1, 1, 1, 1] mid >= target 排除右半边
  }

  return right;
}

int up_bound(vector<int> &nums, int target) {
  int left = 0, right = nums.size();

  while (left < right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] <= target) // [0, 1, 1, 1, 1] 排除左半边
      left = mid + 1;
    else
      right = mid;
  }

  return right;
}