二分查找
#算法 2023-08-23

前提：有序数组

边界条件：根据寻找区间的定义有所不同

  1. 寻找区间为 [left, right]
    • 循环用 while(left ≤ right)，因为当 left == right 时， [left, right] 有意义；
    • 更新用 right = mid - 1 和 left = mid + 1。 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      public int BinarySearch(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left <= right) {
          int mid = left + (right - left) / 2;
          if (nums[mid] > target) {
            right = mid - 1;
          } else if (nums[mid] < target) {
            left = mid + 1;
          } else {
            return mid;
          }
        }
        return -1;
      }
  2. 寻找区间为 [left, right)
    • 循环用 while(left < right)，因为当 left == right 时， [left, right) 无意义；
    • 更新用 right = mid 和 left = mid + 1。 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      public int BinarySearch(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n;
        while (left < right) {
          int mid = left + (right - left) / 2;
          if (nums[mid] > target) {
            right = mid;
          } else if (nums[mid] < target) {
            left = mid + 1;
          } else {
            return mid;
          }
        }
        return -1;
      }