2022.3.23 二分查找

Ted

发布于：2022年3月23日
次浏览

33. Search in Rotated Sorted Array
34. Find First and Last Position of Element in Sorted Array

今天稍微复习一下二分查找。

应用

二分查找主要用于在一系列连续的数中找到指定的一个，通常这一系列数要具有以下一些属性：有序排列且存储在数组中（存储在链表里不能用二分）。

二分查找通过维护查找空间的左右中三个位置，不断通过对中间数与目标数进行比较缩小左右区间。由于每次至少能保证清除掉一半不可能的数，所以时间复杂度为O(logn)。

在leetcode上给了三种二分的模板，目前感觉前两种比较好用。

模板1（l <= r）

首先对于各种模板，通用的一种计算mid的防暑不能忘，因为l + r可能导致整数范围溢出，所以使用l + (r - l) / 2代替。另外在代码中的判断最好全部用if和else if防止漏掉某种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size() - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2; 
    if(nums[mid] == target){ return mid; } // 一般来说不用加上这一行，在退出循环的时候可以判断返回l或r
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

首先是第一种模板，这种模板的主要特点就是判断条件中的(l <= r)，这样只有当l大于r时才会停止循环，换句话说，当最后l == r时，同样会进行一次判断mid(mid == l == r)是不是需要的数。所以，这种方法可以保证对于数据中的每一个数都进行判断，不会有遗漏的数据。

另外这种方法比较容易记，因为起始条件就是标准的，而且每次更新查找范围的话直接使用l = mid + 1, r = mid - 1就可以了。

模板2 (l < r)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size();
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid; }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.size() && nums[left] == target) return left;
  return -1;
}

对于模板二，这个模板的判断条件是(l < r)也就是说当最后l == r的时候就会退出。这个模板在判断的时候维护了一个左闭右开的区间[l, r)，也就是在每次循环的时候最右边的r其实不会被取到（除了最后一次l == r）。因此在实际代码中，每次循环都至少保证了查找空间的大小至少为2，因此我们可以对mid和mid + 1进行访问而不用担心数组下标越界。

但是这个官方模板的起始条件是从r = n开始的，我平时使用r = n - 1感觉也没有问题。

在实际做题中感觉对于查找第一个什么什么数，或者第一次出现的一个pattern比较适合使用这种情况。

比如在278. First Bad Version中，如果mid不是bad version的话就令l = mid + 1，是的话因为mid也有可能是first bad version，所以令r = mid防止将正确答案排除掉。

在162. Find Peak Element中，每次将当前的数nums[mid]和nums[mid + 1]进行比较，如果小于，说明当前在一个上升的“坡”上，继续向前一定会有一个峰值（如果到了数组末尾，因为将数组第n为视作负无穷，数组最后一个值将会是一个峰值），此时就令l = mid + 1，如果大于，则mid有可能是一个峰值，令r = mid防止将mid排除。

在34. Find First and Last Position of Element in Sorted Array中，首先要查找到第一个等于target的数，这样就对于numd[mid]和target进行比较，如果小于的话说明target一定在mid右边，令l = mid + 1，如果大于等于（因为在数组中可能有多个target存在），则mid有可能是第一个target，令r = mid防止删除mid。

但是如果要查最后一个target，直接用模板就不行了。因为如果此时用mid和target比较，因为此时当mid == target时，就只能令l = mid了，这样的话如果最后剩下两个数l,r的时候会导致无限循环。

所以与其找最后一个target，不如找比target大的第一个数。所以在代码里令target + 1，这样即使没有找到的话循环也会停在比target大的第一个数的位置。所以对于numd[mid]和target + 1进行比较，如果小于的话说明target + 1一定在mid右边，令l = mid + 1，如果大于等于的话令r = mid。因为每次寻找的范围都严格大于target，所以即使数组里没有target + 1，循环也会停在最后一个target的下一位。

同时也要记得判断当前位置的数的前一位是不是target，因为如果数组中不存在target的话也能找到一个数，但是这个答案就没有意义了。

另外这道题还有很多种特殊情况需要判断，比如数组第一个或/和最后一个就是target，数组长度为0等等，是一道非常弱智的题。

对于官方给出的模板三，做了一道题感觉实在太麻烦了所以就没记，不过看了别人的教程说这三种模板其实都是一样的所以就不看了。

最后更新于：2022年3月23日

LeetCode

二分查找

评论