二分查找

无重复元素

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
	      int left = 0, right = nums.size() - 1;
          int middle = 0;
          while (left <= right){
              middle = left - (left - right) / 2;
              if (nums[middle] < target)
                  left = middle + 1;
              else if (nums[middle] > target)
                  right = middle - 1;
              else if (nums[middle] == target)
                  return middle;
          }
          return left;
    }
};
 

区间是[left, right] 闭区间。最后 left 和 right 的位置分为两种情况

1. target 在数组中存在： left = right = middle = target
2. target 在数组中不存在： 区间变为[right, left]，target 在中间 例如数组[1, 3, 5, 6], target = 4, 则 right = 1, left = 2; 例如数组[1, 3, 5, 6], target = 0, 则 right = -1, left = 0;

有重复元素

lower bound

    private int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left - (left - right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else if (arr[mid] >= target) {
                right = mid - 1;
            }
        }
        return left;
    }

Higher bound

    private int higherBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left - (left - right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] <= target) {
                left = mid + 1;
            }
	    }
	    return right;
    }