算法：二分查找

1.二分查找

704. 二分查找 - 力扣（LeetCode）

 二分查找算法要确定“二段性”，时间复杂度为O(lonN)。为了防止数据溢出，以是求mid时要用防溢出的方式。

1. class Solution {
2. public:
3.     int search(vector<int>& nums, int target)
4.     {
5.         int left = 0, right = nums.size() - 1;
6.         while(left <= right)
7.         {
8.             //int mid = (left + right) / 2;
9.             int mid = left + (right - left) / 2;//防溢出
10.             if(target > nums[mid])
11.             {
12.                 left = mid + 1;
13.             }
14.             else if(target < nums[mid])
15.             {
16.                 right = mid - 1;
17.             }
18.             else
19.             {
20.                 return mid;
21.             }
22.         }
23.         return -1;
24.     }
25. };

复制代码

淳厚二分模版

2.         while(left <= right)
3.         {
4.             int mid = left + (right - left) / 2;//防溢出
5.             if(......)
6.             {
7.                 left = mid + 1;
8.             }
9.             else if(......)
10.             {
11.                 right = mid - 1;
12.             }
13.             else
14.             {
15.                 return ......;
16.             }
17.         }

复制代码

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

34. 在排序数组中查找元素的第一个和末了一个位置 - 力扣（LeetCode）

用二分查找解决，要查找一个区间要找去左端点和右端点。
1. 查找区间的左端点

细节处理：
        1. 循环条件 left < right 而不是left <= right ，因为left == right 的时候就是最终效果，无需判定。假如判定了就会死循环（当left和right构成的区间中存在效果，并且 nums[mid] >= t时，此时mid也等于left和right，进行上述操作的时候会导致right = mid一直在原地，以是导致死循环）。
        2. 求中点的操作
left + （right - left）/ 2 要向下取整，当剩两个点让mid的指针指向left。

2.查找区间右端点
与查找区间左端点的方法雷同，只是处理条件差异。
1.当nums[mid] <= target 时left == mid。
2.当nums[mid] > target 时right == mid - 1。
循环条件：left < right 和上述原因一致。
求中点的方式 left + (right - left + 1) / 2 要向上取整，当剩两个点让mid的指针指向right。

1. class Solution {
2. public:
3.     vector<int> searchRange(vector<int>& nums, int target)
4.     {
5.         if(nums.size() == 0)
6.             return {-1, -1};
7.         int left = 0, right = nums.size() - 1;
8.         int begin = 0;
9.         while(left < right)//确定区间的左端点
10.         {
11.             int mid = left + (right - left) / 2;//防溢出写法
12.             if(nums[mid] < target)
13.                 left = mid + 1;
14.             else
15.                 right = mid;
16.             
17.         }
18.         //判断是否有结果
19.         if(nums[left] != target)
20.             return {-1,-1};
21.         else
22.             begin = left;
24.         left = 0, right = nums.size() - 1;
25.         while(left < right)//确定区间的右端点
26.         {
27.             int mid = left + (right - left + 1) / 2;
28.             if(nums[mid] <= target)
29.                 left = mid;
30.             else
31.                 right = mid - 1;
32.         }
33.         //如果存在左端点，那么右端点也一定存在，所以不用判断了，直接返回
34.         return {begin, right};
35.         
36.     }
37. };

复制代码

总结二分模版

1.         while(left < right)
2.         {
3.             int mid = left + (right - left) / 2;
4.             if(......)
5.                 left = mid + 1;
6.             else
7.                 right = mid;
8.             
9.         }
11.         while(left < right)//确定区间的右端点
12.         {
13.             int mid = left + (right - left + 1) / 2;
14.             if(......)
15.                 left = mid;
16.             else
17.                 right = mid - 1;
18.         }

复制代码

3. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

 思路：二分查找，用左端点的模版，直接找到查找加返回要插入位置的值。假如未找到target，则检查target是否大于nums[right]：假如是，插入位置为right + 1；否则，插入位置为right（即第一个大于等于target的位置）。

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

复制代码

4. x的平方根

69. x 的平方根 - 力扣（LeetCode）

直接将1 ~ x作为查找区间，找小于等于mid*mid的x的值

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

复制代码

5. 山脉数组的峰顶索引

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

 运用二分查找算法，因为在山脉数组中，在前一段山脉arr[mid] > arr[mid - 1]，在后一段山脉arr[mid] < arr[mid - 1]；根据这个二段性，使用二分查找。

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

复制代码

6. 探求峰值

162. 探求峰值 - 力扣（LeetCode）

运用二分查找算法：对于区间中nums 和 nums[i + 1]，假如nums < nums[i + 1]，那么这段区间程上升趋势，因为nums[-1]和nums[n] = 

,以是在后一段区间内一定有峰值，让left = mid + 1.
假如nums > nums[i + 1]，程下降趋势，在前一段区间内一定有峰值，让right = mid。

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

复制代码

7.探求旋转排序数组中的最小值

153. 探求旋转排序数组中的最小值 - 力扣（LeetCode）

 思路：使用二分查找，因为这个数组是有二段性的（要找的值为第二段的第一个元素），将这个数组分为两段第一段的值一定比第二段的值大，以是根据nums[mid]和nums[n - 1]的关系作为比力。nums[mid]>nums[n - 1]，阐明在mid第一段，以是要让left = mid + 1；nums[mid] <= nums[n - 1]时，阐明mid在第二段上，要让right = mid。
第二种方法是一nums[0]作为比力值，只是这种有特殊环境，满是升序的时候会导致mid一直向后走，以是找特殊判定一下升序的环境。

1. class Solution {
2. public:
3.     int findMin(vector<int>& nums)
4.     {
5.         /*int left = 0, right = nums.size() - 1, n = nums.size();
6.         while(left < right)
7.         {
8.             int mid = left + (right - left) / 2;
9.             if(nums[mid] > nums[n - 1])
10.                 left = mid + 1;
11.             else
12.                 right = mid;
13.         }
14.         return nums[right];*/
16.         int left = 0, right = nums.size() - 1, n = nums.size();
17.         if(nums[n - 1] > nums[0])
18.             return nums[0];
19.         while(left < right)
20.         {
21.             int mid = left + (right - left) / 2;
22.             if(nums[mid] >= nums[0])
23.                 left = mid + 1;
24.             else
25.                 right = mid;
26.         }
28.         return nums[right];
29.     }
30. };

复制代码

8.点名

LCR 173. 点名 - 力扣（LeetCode）

 1.哈希表；2.直接遍历找布局；3.位运算；4.求和公式。这些方法的时间复杂度都是O(N)。
方法5：二分查找：这个数组有二段性，分成两段判定对应的值是否相等，还必要处理一下全升序的环境

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

复制代码

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

继续阅读请点击广告