【二分查找】
定义:
二分查找也称折半查找(Binary Search),是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知,运用二分搜索的前提是数组必须是有序的,这里需要注意的是,我们的输入不一定是数组,也可以是数组中某一区间的起始位置和终止位置。
前言:
二分查找的思路不难理解,但是里面有许多细节问题需要注意,比如边界条件,循环结束条件中 left 和 right 的关系,更新 left 和 right 位置时要不要加 1 减 1。下面的三种模板,是从其他博客整理到的,但是实际上掌握一种就行,主要需要注意细节问题,不管哪种模板一定要判断的是 下一轮「向左找」还是「向右找」,还有 mid 是不是有可能是问题的答案,这一点应该从题目中分析得到,所以一定要认真审题~
二分查找法两种模板写法:
模板一:
while (left <= right) ,这种写法里面的 left 和 right 都要加 1 或者减 1,还要判断 mid 位置的值有可能是解的时候,把 mid 的值保存下来,退出循环以后 left 在右,right 在左,即left == right + 1,写成区间 [left..right] ==> [right+1, right]为空区间,表示没找到,直接返回-1即可;
1 class Solution { 2 public int searchInsert(int[] nums, int target) { 3 int left = 0, right = nums.length - 1; 4 while(left <= right) { // 注意 5 int mid = left + (right - left) / 2; 6 if(nums[mid] == target) {
7 return mid; 8 } else if(nums[mid] < target) { 9 left = mid + 1; // 注意 10 } else { 11 right = mid - 1; // 注意 12 } 13 } 14 // 相关返回值 15 return -1; 16 } 17 }
模板二:
while (left < right) ,这种写法的好处是在循环结束的时候不用判断应该返回left还是right。因为循环结束的条件是 left == right,区间 [left..right] 有 1 个元素,如果可以确定区间[left, right]一定有解,直接返回left即可,否则需要对left这个位置的元素单独判断一次。
搜索区间[left, right]是配对形式存在的:
- 要么是[left, mid-1]和[mid, right]即left = mid 与 right = mid - 1,mid需要向上取整:mid = left + (right - left) / 2 ;
- 要么是[left, mid]和[mid+1, right]即left = mid + 1 与 right = mid ;
小提醒:在写相关逻辑语句的时候,可以在注释里写上「下一轮搜索区间是什么」。如果下一轮搜索区间是 [mid..right] ,这个时候就设置 left = mid,这种情况的反面区间就是 [left..mid - 1] ,那么 else 就设置 right = mid - 1,所以就不用记忆配对关系了。
1 class Solution { 2 public int searchInsert(int[] nums, int target) { 3 int left = 0, right = nums.length - 1; 4 while(left < right) { // 注意 5 int mid = (left + right) / 2; // 注意 6 if(nums[mid] <= target) { 7 // 相关逻辑 8 left = mid + 1 9 } else { 10 right = mid; // 注意 11 } 12 } 13 // 相关返回值 14 return nums[left] == target ? left : -1; 15 } 16 }
【向上取整】与【向下取整】
向上取整与向下取整主要是为了处理当只剩下两个元素的情况,这时 left 和 right 相差1。
向上取整:把整个区间划分成[left, mid -1] 和 [mid, right],把mid划分给了右区间,如果操作是选择了包含mid的这个区间,那么就需要mid值来更新left,如果向下取整,left和right值算出来的mid就与left相等(例如:(4+5) / 2 == 4),再将left更新成mid,相当于没有更新left,故需要向上取整,算出来的mid值与right相等,这样left向右移动,得到更新,和right指向相同的值。
向下取整:把整个区间划分成[left, mid] 和 [mid + 1, right],把mid划分给了左区间,如果操作是选择了包含mid的这个区间,那么就需要mid值来更新right,如果向上取整,left和right值算出来的mid就与right相等(例如:(5 + 4) / 2 +1 == 5),再将right更新成mid,相当于没有更新right,故需要向下取整,算出来的mid值与left相等,这样right向左移动,得到更新,和left指向相同的值。
总结:
mid如果被分给了右区间,需要向上取整,保证left能够被新值更新。
mid如果被分给了左区间,需要向上取整,保证left能够被新值更新。
标签:总结,二分,right,int,mid,取整,区间,模板,left From: https://www.cnblogs.com/liu-myu/p/16889741.html