二分法查找

二分法查找算法应用的条件：

• 数组按照顺序排列【基础】；
• 数组中没有重复的元素【否则返回值元素的下标不唯一】；

二分法查找主要难点在于边界条件的确定，常见的区间的定义一般有两种：左闭右闭，即 [left, right]，或者左闭右开，即 [left, right)；

第一种：左闭右闭，即 [left, right]，代码如下：

class Solution {
    public int search(int[] nums, int target) {
        int res = -1;
        int right = nums.length -1;
        int left = 0;
        while (left <= right) {            //重点在于循环条件的确定；
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle -1;
            }
            else if (nums[middle] < target) {
                left = middle +1;
            }
            else {
                res = middle;
                break;
            }
        }
        return res;
    }
}

第二种：左闭右开，即 [left, right)，代码如下：

class Solution {
    public int search(int[] nums, int target) {
        int res = -1;
        int right = nums.length;
        int left = 0;
        while (left < right) {				//循环条件的确定
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle;
            }
            else if (nums[middle] < target) {
                left = middle +1;
            }
            else {
                res = middle;
                break;
            }
        }
        return res;
    }
}

两种方法的区别：

• 左闭右闭，即 [left, right]，
  • 当left = right时，仍然要进入循环；
  • 当没有找到 target 值时，循环体结束后，left - right = 1；
• 左闭右开，即 [left, right)，
  • 当left = right时，跳出循环；
  • 当没有找到 target 值时，循环体结束后，right = left；

此外，涉及到边界条件问题：

• 例如：在排序数组中查找元素的范围【数组非严格单调，存在重复元素】，此时，需要确定范围的左右区间；

• 区间的确定：

  \[左区间：nums[pos−1]<target≤nums[pos]\\ 右区间：nums[pos−1]≤target<nums[pos] \]

• 当为左闭右闭，即 [left, right]时：

  public int getRight(int[] nums, int target) {
          int res = -1;
          int right = nums.length - 1;
          int left = 0;
          while (right >= left) {
              int middle = left + ((right - left) >> 1);
              if (nums[middle] > target) {
                  right = middle -1;
              }
              else {
                  left = middle + 1;
              }
          }
          res = left;
          }
          return res;
      }
  public int getLeft(int[] nums, int target) {
          int res = -1;
          int right = nums.length - 1;
          int left = 0;
          while (right >= left) {
              int middle = left + ((right - left) >> 1);
              if (nums[middle] < target) {
                  left = middle + 1;
              }
              else {
                  right = middle -1;
              }
          }
          res = right;
          return res;
      }
  

  • 循环体结束后，left - right = 1；

  • 当数组不存在对应target元素时，左右区间产生的left，right完全一样；

  • 当数组中存在一个元素时

    • left - right = 1；

    • \(right_{左区间}\) = \(left_{右区间}\)

    • 由上面两个公式，可得：

      \(right_{右区间} - left_{左区间}=2\)

  • 当数组中存在多个元素时，同理：

    • \(right_{右区间} - left_{左区间}=2 + 元素个数\)

  • 统一范围：[\(left_{左区间} +1, right_{右区间} -1\)]，

• 当为左闭右开，即 [left, right)时，代码如下：

      public int getRight(int[] nums, int target) {
          int res = -1;
          int right = nums.length;
          int left = 0;
          while (right > left) {
              int middle = left + ((right - left) >> 1);
              if (nums[middle] > target) {
                  right = middle;
              }
              else {
                  left = middle + 1;
              }
          }
          res = left;
          return res;
      }
      public int getLeft(int[] nums, int target) {
          int res = -1;
          int right = nums.length;
          int left = 0;
          while (right > left) {
              int middle = left + ((right - left) >> 1);
              if (nums[middle] < target) {
                  left = middle + 1;
              }
              else {
                  right = middle;
              }
          }
          res = right;
          return res;
      }
  

  • 循环体结束后，left = right，并且最后一步骤基本都是 left = left + 1；
  • 当数组不存在对应target元素时，
    • target元素在数组的范围内，但不存在时，left = right=靠近较大值的索引，例如：nums = [0, 0, 2, 2]，target = 1, \(left = right = 2_{index}\)
    • target元素不在数组的范围内，且不存在时，left = right = 0 or nums.length；
  • 当数组中存在一个元素时:
    • 左区间：$left_{右区间} = right_{右区间} $ = 元素索引；
    • 右区间： $left_{右区间} = right_{右区间} $ = 元素索引 + 1；
    • 因为当left和right相邻的时候，middle取的是 left的值作为索引，而左闭右开，则还会执行一次；
  • 当数组中存在多个元素时，
    • 左区间：$left_{右区间} = right_{右区间} $ = 元素索引；
    • 右区间： $left_{右区间} = right_{右区间} $ = 元素索引 + 元素个数；
  • 统一范围：[$left_{左区间} , right_{右区间} -1 $]；