title: LC101の3. 二分
urlname: cyq5ys
date: ‘2021-05-24 15:29:18’
tags: [二分]
categories: [算法刷题]

算法解释

每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。
对于一个长度为 O(n) 的数组，二分查找的时间复杂度为 O(log n)。

寻找 target 的第一次出现（即 >=target）模板：

左闭右开：l < r相当于在[l, r)区间内搜索

  1. int ler_bound(vector<int>& nums, int target){
  2.     int l = 0, r = nums.size();
  3.     while(l < r){
  4.         int mid = (l + r) >> 1;    
  5.         if(nums[mid] < target){
  6.             l = mid + 1;
  7.         }else{
  8.             r = mid;
  9.         }
  10.     }
  11.     return l;
  12. }

冷知识：虽然早在1946 年就有人将二分查找的方法公诸于世，但直到1962 年才有人写出没有bug 的二分查找程序

⭐友情链接：

二分查找的细节(左闭右闭、左闭右开、左开右闭)及其两段性

详解二分查找 ，二分查找细节详解 - 知乎 (zhihu.com)

求开方

69. x 的平方根

题目大意：返回非负整数x的算术平方根

思路：二分模板题，防止越界 x < mid * mid 换成 x / mid < mid 写法，==的情况可以合并到上面两种其一

  1. int mySqrt(int x) {
  2.     int l = 1, r = x;
  3.     while(l <= r){
  4.         int mid = l + (r - l) / 2;
  5.         if(x /mid < mid ){
  6.             r = mid - 1;
  7.         }else if(x / mid > mid){
  8.             l = mid + 1;
  9.         }else{
  10.             return mid;
  11.         }
  12.     }
  13.     return r;
  14. }

查找区间

34. 在排序数组中查找元素的第一个和最后一个位置

题目大意：输出数字第一次和最后一次出现位置（即手动实现leer_bound和upper_bound）
输入输出： nums = [5,7,7,8,8,10], target = 8 => [3,4]
思路：可以理解为寻找 >=target 的第一个和 >target 的第一个然后减一

  1. vector<int> searchRange(vector<int>& nums, int target) {
  2.     if(nums.empty())return vector<int>{-1, -1};
  3.     int ler = ler_bound(nums, target);
  4.     int upper = ler_bound(nums, target + 1) - 1;
  5.     if(ler == nums.size() || nums[ler] != target){
  6.         return vector<int>{-1, -1};
  7.     }
  8.     return vector<int>{ler, upper};
  9. }
  10. int ler_bound(vector<int>& nums, int target){
  11.     int l = 0, r = nums.size();
  12.     while(l < r){
  13.         int mid = (l + r) >> 1;
  14.         if(nums[mid] < target){
  15.             l = mid + 1;
  16.         }else{
  17.             r = mid;
  18.         }
  19.     }
  20.     return l;
  21. }

旋转数组查找数字

81. 搜索旋转排序数组 II

题目大意：判断目标数是否在旋转数组中
输入输出：nums = [2,5,6,0,0,1,2], target = 0 => true
思路：题目与普通的二分唯一不同在于数组的有序被切成两份，尾巴接到头部，即旋转数组

当num[l] == num[mid]时，无法判断哪边有序，l++

当num[l] <= num[mid]时，左边有序，

当num[l] > num[r]时，右边有序，

  1. bool search(vector<int>& nums, int target) {
  2.     int l = 0, r = nums.size() - 1;
  3.     while(l <= r){
  4.         int mid = (l + r) >> 1;
  5.         if(nums[mid] == target){
  6.             return true;
  7.         }
  8.         if(nums[l] == nums[mid]){
  9.             l++;
  10.         }else if(nums[l] < nums[mid]){
  11.             if(nums[l] <=target && nums[mid] > target){
  12.                 r = mid - 1;
  13.             }else{
  14.                 l = mid + 1;
  15.             }
  16.         }else{
  17.             if(nums[mid] < target && nums[r] >= target){
  18.                 l = mid + 1;
  19.             }else{
  20.                 r = mid - 1;
  21.             }
  22.         }
  23.     }
  24.     return false;
  25. }

练习

153. 寻找旋转排序数组中的最小值

题目大意：输入互不相同的数组由升序数组旋转 n 次得到，求最小元素

输入输出：[3,4,5,1,2] => 1

思路：官方图解 - 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

当mid小于最右值时，最小值在 mid左边可能等于mid

当mid大于最右值时，最小值 在mid右边，联想两段直线关系，不可能等于mid，或者说它都已经比最右值大了怎么可能是最小值…

  1. class Solution {
  2. public:
  3.     int findMin(vector<int>& nums) {
  4.         int l = 0, r = nums.size() - 1;
  5.         while (l < r) {
  6.             int mid = l + (r - l) / 2;
  7.             if (nums[mid] < nums[r]) {
  8.                 r = mid;
  9.             }
  10.             else {
  11.                 l = mid + 1;
  12.             }
  13.         }
  14.         return nums[l];
  15.     }
  16. };

154. 寻找旋转排序数组中的最小值 II

题目大意：输入数组由升序数组旋转 n 次得到，求最小元素
输入输出：nums = [1,3,5] => 1
思路：官方图解 - 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）

区别于上一题的地方是存在重复的值，精髓是采用r—

理解r—，等同于证明为什么原本的nums[r]一定不是最小值？

  1. int findMin(vector<int>& nums) {
  2.     int l = 0, r = nums.size()-1;
  3.     while(l < r){
  4.         int mid = l + (r - l) / 2;
  5.         if(nums[mid] < nums[r]){
  6.             r = mid;
  7.         }else if(nums[mid] > nums[r]){
  8.             l = mid + 1;
  9.         }else{
  10.             r--;
  11.         }
  12.     }
  13.     return nums[l];
  14. }

540. 有序数组中的单一元素

题目大意：求只出现一次的数
输入输出：nums = [1,1,2,3,3,4,4,8,8] => 2
思路：补足缺失的元素，数组满足mid 是偶数，mid + 1是奇数；mid是奇数，mid - 1是偶数。

因此，只要不满足如上条件，就可以判断出哪边缺了元素。

ps：这两种情况也可以使用异或来进行合并，因为偶数异或1等于+1，奇数异或1等于-1。

  1. class Solution {
  2.     public int singleNonDuplicate(int[] nums) {
  3.         // 二分查找
  4.         int l = 0, r = nums.length - 1;
  5.         while (l < r) {
  6.             int mid = (l + r) / 2;
  7.             if (mid % 2 == 0) {
  8.                 if (nums[mid] == nums[mid + 1]) {
  9.                     l = mid + 1;
  10.                 } else {
  11.                     r = mid;
  12.                 }
  13.             } else {
  14.                 if (nums[mid] == nums[mid - 1]) {
  15.                     l = mid + 1;
  16.                 } else {
  17.                     r = mid;
  18.                 }
  19.             }
  20.         }
  21.         return nums[r];
  22.     }
  23. }
  24. 优化成异或：
  25. class Solution {
  26.     public int singleNonDuplicate(int[] nums) {
  27.         // 二分查找
  28.         int l = 0, r = nums.length - 1;
  29.         while (l < r) {
  30.             int mid = (l + r) / 2;
  31.             if (nums[mid] == nums[mid ^ 1]) {
  32.                 l = mid + 1;
  33.             } else {
  34.                 r = mid;
  35.             }
  36.         }
  37.         return nums[r];
  38.     }
  39. }