二分算法——优选算法

个人主页：敲上瘾-CSDN博客
  个人专栏：游戏、数据结构、c语言基础、c++学习、算法
          本章我们来学习的是二分查找算法，二分算法的应用非常广泛，不但限于数组查找，还可以用于办理各种搜索题目、查找极值题目等。在数据结构和算法中，它是基础且重要的算法之一。
接下来我准备了三个题来引出并学习该算法，末了来做总结。
目录
一、二分查找
1.题目解析
2.算法原理
3.代码编写
二、查找元素的首末位置
1.题目解析
2.算法原理
3.代码编写
三、探求峰值
1.题目解析
2.算法原理
3.代码编写
四、总结

---

一、二分查找

1.题目解析

        该题目要求是给一个元素target然后在升序数组nums中找到该元素的下标，若不存在则返回-1。题目要求简单易懂就不再多讲，这里要注意两个点：(1)、数组是升序的。(2)、须要返回的是元素下标。
2.算法原理

        对于该题最容易想到的解法就是把数组从头到尾遍历一遍，时间复杂度为O(N)。
        解法二：因为这个数组是有序的所以我们可以用二分的思想，起首使用三个指针（这里指的是数组的下标）left，right，mid，其中left和right维护一段区间，把目标值锁定到[left，right]区间内。mid表示区间的中心下标，把区间一分为二。
        接下来锁定target的位置：假如target小于mid下标指向的元素，那么因为数组是升序，所以target一定在区间[left，mid]中，即right更新为mid，然后更新mid（ mid=left+(right-left)/2 ）。              假如target大于mid指向元素，那么target一定在区间[mid，right]中，即把left更新为mid，然后更新mid。重复操作直到left>right。
如下：

该算法的时间复杂度为logN，证明如下：

3.代码编写

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) right=mid-1;
11.             else if(nums[mid]<target) left=mid+1;
12.             else return mid;
13.         }
14.         return -1;
15.     }
16. };

复制代码

二、查找元素的首末位置

1.题目解析

        该题的题目要求与上一题类似，都是在升序数组中查找元素，不外该题查找的是元素第一次出现的位置和末了一次出现的位置。这里还要求时间复杂度为O(logN)，这里就很明显地提示了该题要使用二分算法。
2.算法原理

        同样的此题可以使用暴力罗列来办理，不外时间复杂度为O(N)，根据上题的经验这里我们还是思量使用二分法。不外也很容易发现把上面的算法原模原样搬过来是办理不了该道题的，我们只能找到target元素的是无法锁定它第一次出现的位置和末了一次出现的位置。我们可以用以下解法：
   左边界查找：
          当mid指向的元素为target的时候，不消返回，而是让right更新为mid，mid指向元素大于target时同样更新right为mid，即可以归并为
          if(nums[mid]>=target)   right=mid;
  当mid指向元素小于target时left更新为mid+1，重复该操作就可以把数组右边的target忽略，锁定最左边的target。这里做循环的时候须要注意循环条件不能是left<=rigth，假如是left<=right就可能使mid不停赋值给right从而进入死循环，所以我们使用left<right。
  
  右边界查找：
          当mid指向的元素为target的时候，不消返回，而是让left更新为mid，mid指向元素小于target时同样更新left为mid，即可以归并为
          if(nums[mid]<=target)   left=mid;
  当mid指向元素大于target时right更新为mid-1，重复该操作就可以把数组左边的target忽略，锁定最右边的target。这里做循环的时候同样须要注意循环条件只能是left<rigth。
  注意：当元素只有两个时使用mid=left+(right-left)/2盘算的mid就是第一个元素，那么也就是mid==left，假如mid指向的元素为target时把mid赋值给left（即left=mid）相当于什么也没干，程序同样会进入死循环。所以我们使用mid=left+(right-left+1)/2盘算mid。
          以上的两个查找法险些可以办理所有的二分算法题，可以作为一个模板记忆，在总结部分我会给出模板。
3.代码编写

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.         while(left<right)
9.         {
10.             int mid=left+(right-left)/2;
11.             if(nums[mid]>=target) right=mid;
12.             else left=mid+1;
13.         }
14.         if(nums[left]!=target) return {-1,-1};
15.         int n=left;
16.         right=nums.size()-1;
17.         while(left<right)
18.         {
19.             int mid=left+(right-left+1)/2;
20.             if(nums[mid]<=target) left=mid;
21.             else right=mid-1;
22.         }
23.         return {n,left};
24.     }
25. };

复制代码

三、探求峰值

1.题目解析

该题要求我们返回恣意峰值，比如把数组元素抽象成连续的数据如下：

须要返回以上红圈部分的恣意一点， 也就是该元素至少要满足它左边的第一个元素和右边的第一个元素都要小于它。
注意：题目给的信息nums[-1]和nums[n]为负无穷，所以不要忽略以下环境：

2.算法原理

        这题同样可以使用暴力罗列，时间复杂度为O(N)，该解法就不再多讲。
        这个题与上两个题有一个很大的区别是该数组并不是有序的，但是不要紧该题同样可以使用二分的思想，注意许多人会误认为二分算法只能用在有序的数组中，而事实并不局限于此，只须要找到数据的二段性即可，如该题我们可以如许：

        该方法也就是上一题的右边界查找，固然也可以使用左边界查找的方法，但用质朴的二分查找办理不了该题。
3.代码编写

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. };

复制代码

四、总结

1、二分算法并不局限于数组有序，只要找到数据的二段性即可使用二分算法。
2、二分算法模板
   2.1.质朴二分模板

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 ...
7. }

复制代码

2.2.左边界查找模板

1. while(left<right)
2. {
3.     int mid=left+(right-left)/2;
4.     if(...) left=mid+1;
5.     else right=mid;
6. }

复制代码

2.3.右边界查找模板

1. while(left<right)
2. {
3.     int mid=left+(right-left+1)/2;
4.     if(...) left=mid;
5.     else right=mid-1;
6. }

复制代码

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