二分查找一般解法

二分查找模板

二分查找一般容易犯错的地方有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;
}

参考文章:

comments powered by Disqus