算法-二分查找

 说到二分查找算法，我们常常会想到用一个排序过的数组，但是其实二分查找不只能在有序数组中carry，只要观察出规律，很多情况都可以用二分思想快速解决问题，想要熟悉并且用好二分查找算法的思想，这篇文章已经够了。

第一题

二分查找

 这道题和我们的算法思想叫做同一个名字，所以这道题是了解二分查找算法首选的一道题，我想很多人都已经了解过了二分查找算法。

 因为是有序数组，所以每次都能排除从中间位置查找都能够舍去一半的可能性，所以查找的时间复杂度只需要logⁿ即可，如果从头到尾就需要O(N)的时间复杂度。

一个优化点
求mid时，可以这样用来防止溢出

一个小技巧
 我们在选取mid时，如何判断怎么走left和rigth，相遇时才不会出现死递归的情况呢？
 证明的话比较复杂，我们只需要记住，下边是很重要的，后边的题目都会用到。

上边右边的情况应该是right=mid-1;
 而且一般需要left停在我们想要的位置，所以判断条件left位置应加上等于，会在下边的题解中提到。

举一个例子

上边求mid的式子，主要是为了防止溢出。

 如果查找的过程中一直找不到关键字，那么直到left和right相遇后跳出循环，然乎判断相遇出的位置是否为我们要找的数字，如果不是就表示我们要找的数组中并没有这个值，如果找到就返回left（下标）
呐，暴力解法

再来看二分查找

代码如下

int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1,mid=left+(right-left)/2;
        while(left<right)
        {
            if(nums[mid]<target)
            {
                left=mid+1;
            }
            else
            {
                right=mid;
            }
            mid=left+(right-left)/2;//这是取中若是奇数就直接用的情况。
        }
        if(nums[left]!=target)
        {
            return -1;
        }
        return left;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

下边是相加和为奇数，除以2得到结果加1的情况。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1,mid=left+(right-left+1)/2;
        while(left<right)
        {
            if(nums[mid]<=target)
            {
                left=mid;
            }
            else
            {
                right=mid-1;
            }
            mid=left+(right-left+1)/2;

        }
        if(nums[left]!=target)
        {
            return -1;
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

 大家可以比较一下区别，也可以在本子上画一画这是如何控制相遇时不会死循环的。

第二题

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

这还是一道二分查找题，逻辑稍微复杂一点，还是练习我们的代码实现能力。
就像第一个例子，在数组中查找8，我们有两种思路，先找到左边的元素，然后找右边的元素，然后锁定右边的元素，直接查找左边的元素。另一种思路就是反过来。
当然，在找到一端的位置后，就使用一个变量保留该位置，然后继续使用二分查找寻找另一端的位置。
左端和右端不同的是该值大于前边的值或者是小于后边的值。
上边所说的很容易理解，接下来我们就开始写代码了。

class Solution {
public://我想知道简便方法
vector<int> searchRange(vector<int>& nums, int target)
{
    // 处理边界情况
    if(nums.size() == 0) return {-1, -1};
    int begin = 0;
    // 1. ⼆分左端点
    int left = 0, right = nums.size() - 1;
    while(left < right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    // 判断是否有结果
    if(nums[left] != target) return {-1, -1};
    else begin = left; // 标记⼀下左端点
    // 2. ⼆分右端点
    left = 0, right = nums.size() - 1;
    while(left < right)
    {
        int mid = left + (right - left + 1) / 2;
        if(nums[mid] <= target) left = mid;
        else right = mid - 1;
    }
    return {begin, right};
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

要注意细节问题，就比如这道题的长度，如果第一次查找size=0就直接返回-1,-1，还有就是第一次查找如果没有查找到就直接返回-1,-1。

第三题

山脉数组的峰顶索引

这道题目就不是在数组有序的情况下来完成的，使用二分查找我们要找到一定的规律就可以，来解析这道题

使用二分查找法，如果查找到3的位置，可以发现3是大于左边的0，小于右边的7，如果查找到2，他就是小于左边的，大于右边的，根据这个特性，我们就还是可以使用二分查找算法来完成这道题。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        //寻找山峰位置的元素
        int left=0,right=arr.size()-1;
        int mid=0;
        while(left<right)
        {
            mid=left+(right-left)/2;
            if(arr[mid]<arr[mid+1])
            {
                left=mid+1;
            }
            else
            {
                right=mid;
                if(arr[mid]>arr[mid-1])
                {
                    return mid;
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

这道题就是前边我们所说，二分查找并不是只有在数组有序的情况下才能使用的，只要我们发现需要查找的对象中元素是否有某种规律，我们就可以使用二分查找迅速来解决问题。

第四题

寻找峰值

这道题和前边的寻找峰值十分类似，我们不需要担心存在多个峰值，我们只需要寻找规律就可以了。
来画图观察一下规律

在这个曲线上随机选取某点，观察规律，思考如何快速找到峰值并且不会出现错误判断。
第一种情况就是右边的值大于该点的值。

还有一种情况就是查找到的值右边小于该点的值，

这道题目要求的是返回任何一个峰值元素就可以，所以我们就不用考虑这么多，接下来就可以上手写代码了。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size()==1)//如果只有一个元素，那就直接返回0
        {
            return 0;
        }
    int left = 0, right = nums.size() - 1;
    int mid = 0;
    while (left < right)
    {
        mid = left + (right - left) / 2;
        if(nums[mid]<nums[mid+1])//下边两种请况
        {
            left=mid+1;
        }
        else
        {
            if(mid==0||nums[mid]>nums[mid-1])
            {
                return mid;
            }
            else
            {
                right=mid;
            }
        }
    }
    return left;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

二分查找不只是可以在数组中查找某值或者某特殊位置，在别的问题中使用也能达到很不错的效果。

第五题

寻找旋转数组中的最小值

这道题同样不是一个有序数组，而是一个半有序数组，但是我们还是可以用二分查找的思想来解决它。
还是找规律

当然还有一种情况，当数组旋转次数和数组元素一样，此时数组还是一个升序数组，这种特殊情况我们也可以判断。
首先说一下思路
还是定义一个left和一个right，当mid位置的元素大于第一个元素时，表明在第一个区间，就将left改到mid加1的位置，如果小于，就将right更新到mid的位置。当left和right相遇时就得到了正式答案。
当然有可能是一个升序数组，这样会一直向后更新left，相遇时就到达了最后一个元素，此时0位置的元素才是我们想要的结果，返回0就可以。
代码如下

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

第六题

x的平方根

这道题目不允许使用内置函数和运算符，暴力解法的话，只需要在0到x间不断循环，直到找到一个数的平方刚好小于等于x;
另一种解法就是二分查找
这道题还不能用我们上边的判断left最后位置的方法

if(mid*mid<x)
{
	left=mid+1;
}
1
2
3
4

如果用这种方法的话，在平方刚好小于x的位置上还会继续向后移动，所以我们选择另外一种。

if(mid*mid<=x)
{
    left=mid;
}
1
2
3
4

这样left所在位置的平方和就刚好是最近的小于等于x的。
代码如下

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

这道题如果mid不用long long就会超出int的范围，以至于不能通过全部用例。本题结束。