二分查找一般解法

二分查找模板

二分查找一般容易犯错的地方有3个：

• 应该给mid加1还是应该减1，还是不加不减
• 上层的while循环里面的条件应该是left < right 还是 left <= right
• 计算mid时，最好是采用mid = left + (right - left)/2而不是mid = (left + right) /2。因为这样可以避免int溢出。

二分查找的一般框架为：

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

上面框架中省略的地方，其实就是比较容易出问题的地方。

下面直接给出二分查找的算法模板，一般只需要熟记其中之一就好了。我一般都采样第一个：

总结一下2个模板的记忆方法：

• 如果初始化right = nums.length -1, 那么使用left <= right，并且right = mid - 1
• 如果初始化right = nums.length那么使用left < right, 并且right = mid

模板1

int binarySearch(int[] nums, int target) {
	int left = 0;
    int right = nums.length - 1; //注意
    
    while( left <= right ) { //注意
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) {
          //找到目标值的相关逻辑
          return mid;
      } else if (nums[mid] < target) {
          left = mid + 1;  //注意
      } else if (nums[mid] > target) {
          right = mid - 1; //注意
      }
    }
    //没找到目标值的相关逻辑
    return -1;
}

模板2

int binarySearch(int[] nums, int target) {
	int left = 0;
    int right = nums.length;  //注意
    
    while( left < right ) { //注意
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) {
          //找到目标值的相关逻辑
          return mid; 
      } else if (nums[mid] < target) {
          left = mid + 1;
      } else if (nums[mid] > target) {
          right = mid //注意
      }
    }
    //没找到目标值的相关逻辑
    return -1;
}

下面通过一些例子来使用一下模板

寻找一个数

这个场景是最简单的，肯能也是大家最熟悉的，即在递增序列中搜索一个数，如果存在，返回其索引，否则返回 -1。

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

LeetCode上面有一个题目，[374. 猜数字大小] 其实就是最简单和标准的二分查找算法。

二分查找的变种问题

查找左右边界

这类题目一般的特点为：

• 数组有序，但是有重复元素
• 数组部分有序，不包含重复元素
• 数组部分有序，包含重复元素。

查找左边界

既然要寻找左边界，搜索范围就需要从右边开始，不断往左边收缩，也就是说即使我们找到了nums[mid] == target, 这个mid的位置也不一定就是最左侧的那个边界，我们还是要向左侧查找，所以我们在nums[mid]偏大或nums[mid]就等于目标值的时候，继续收缩右边界, 不过需要注意最终while循环外需要外检查一下边界情况。

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

查找右边界

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况，见下图
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

参考文章：

• [我作了首诗，保你闭着眼睛也能写对二分查找]
• [二分查找、二分边界查找算法的模板代码总结]