二分查找算法

二分查找

1. class Solution
2. {
3. public:
4.     int search(vector<int>& nums, int target)
5.     {
6.         int left = 0, right = nums.size() - 1;
7.         while(left <= right) // 等于也要进入循环
8.         {
9.             int mid = left + (right - left) / 2; // 防止溢出
10.             if(nums[mid] < target) left = mid + 1;
11.             else if(nums[mid] > target) right = mid - 1;
12.             else return mid;
13.         }
14.         return -1;
15.     }
16. };

复制代码

总结：

• 能利用二分查找的前提是具有二段性，无论是否有序，紧张的是有二段性
  
• 判定循环的条件要注意，即是的时候也要进入循环，因为都是未知的，当left和right相等时，具体到一个数也要进循环判定
  
• 在算mid时要防止溢出
  
• 本题也是朴素二分查找的模板
  

1. while(left <= right) // 等于也要进入循环
2. {
3.    int mid = left + (right - left) / 2; // 防止溢出
4.    if(...) left = mid + 1;
5.    else if(...) right = mid - 1;
6.    else return ...;
7. }

复制代码

• …根据二段性来填写
  

在排序数组中查找元素的第一个和末了一个位置

1. class Solution
2. {
3. public:
4.     vector<int> searchRange(vector<int>& nums, int target)
5.     {
6.         if(nums.size() == 0) return {-1, -1};
7.         int left = 0, right = nums.size() - 1;
8.         int begin = 0; // 用于记录左端点
9.         // 找左端点
10.         while(left < right)
11.         {
12.             int mid = left + (right - left) / 2;
13.             if(nums[mid] < target) left = mid + 1;
14.             else right = mid;
15.         }
16.         if(nums[left] != target) return {-1, -1};
17.         else begin = left;
18.         // 找右端点
19.         left = 0, right = nums.size() - 1; // 重置指针
20.         while(left < right)
21.         {
22.             int mid = left + (right - left + 1) / 2;
23.             if(nums[mid] <= target) left = mid;
24.             else right = mid - 1;
25.         }
26.         return {begin, right};
27.     }
28. };

复制代码

总结：

• 模板
  

1. // 找左端点
2. while(left < right)
3. {
4.     int mid = left + (right - left) / 2;
5.     if(...) left = mid + 1;
6.     else right = mid;
7. }
9. // 找右端点
10. left = 0, right = nums.size() - 1; // 重置指针
11. while(left < right)
12. {
13.     int mid = left + (right - left + 1) / 2;
14.     if(...) left = mid;
15.     else right = mid - 1;
16. }

复制代码

助记：下面-1，上面就加一，判定环境就题论题

• 
  
  

x的平方数

1. class Solution
2. {
3. public:
4.     int mySqrt(int x)
5.     {
6.         if(x == 0) return 0;
7.         int left = 1, rigth = x;
8.         while(left < rigth)
9.         {
10.             long long mid = left + (rigth - left + 1) / 2; // 防止溢出
11.             if(mid * mid <= x) left = mid;
12.             else rigth = mid - 1;
13.         }
14.         return left;
15.     }
16. };

复制代码

总结：

• 提前处理边界环境
  
• 本题实际上是找左端点，所以想左端点紧张，写出判定条件
  

搜索插入位置

1. class Solution
2. {
3. public:
4.     int searchInsert(vector<int>& nums, int target)
5.     {
6.         // 实际上是找右端点
7.         int left = 0, right = nums.size() - 1;
8.         while(left < right)
9.         {
10.             int mid = left + (right - left) / 2;
11.             if(nums[mid] < target) left = mid + 1;
12.             else right = mid;
13.         }
14.         if(nums[left] < target) return left + 1;
15.         return left;
16.     }
17. };

复制代码

总结：
本题实际是找左端点，需要注意的是要单独处理一下末了的特殊环境
山脉数组的峰顶索引

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

复制代码

总结：

• 数组具有二段性，想到二分查找
  
• 直接用模板，下面减一上面加一
  

探求峰值

1. class Solution
2. {
3. public:
4.     int findPeakElement(vector<int>& nums)
5.     {
6.         int left = 0, right = nums.size() - 1;
7.         while(left < right)
8.         {
9.             int mid = left + (right - left) / 2;
10.             if(nums[mid] > nums[mid + 1]) right = mid; //如果中间值大于下一个值，就去左边一段查找，体会二段性
11.             else left = mid + 1; // 否则去右边一段查找
12.         }
13.         return left;
14.     }
15. };

复制代码

总结：
3. 上减下加，模板很固定，没有出现则不用加
4. 存在二段性就能用二分查找，不用管数组是否有序
探求旋转排序数组的最小值

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

复制代码

总结：
5. 本题主要是找见二段行，肯定要绘图，理解两段，找见参照点
点名

1. class Solution
2. {
3. public:
4.     int takeAttendance(vector<int>& records)
5.     {
6.         int left = 0, right = records.size() - 1;
7.         while(left < right)
8.         {
9.             int mid = left + (right - left) / 2;
10.             if(records[mid] == mid) left = mid + 1;
11.             else right = mid;
12.         }
13.         return records[left] == left ? left + 1 : left; // 三目表达式的运用很方便
14.     }
15. };

复制代码

总结：

• 本题解法许多，如利用哈希表，遍历，位运算（异或），数组求和，二分法
  
• 二分法关键是找二段性，本题的二段性在值和下标是否一一对应，注意要处理边界环境
  

---

完

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。