算法模型总结：二分查找

一、最基本的二分查找

[704. 二分查找]

通过对基本的二分查找的分析，我们可以总结变式的来源。

1.二分查找的应用场景

1.数组是有序的。

2.数组中的元素不重复。

所谓查找，本质就是每一次排除一批数据。因此往往也伴随着需要分类讨论。

2.二分查找核心书写思路

• 首先需要处理要查找的元素在数组范围外的部分，即没有找到。

• 然后在数组中进行二分查找。

• [left,right]：区间为left和right，其中它们都是数组下标。

• while(left<=right)：这是因为下标为left=right的这个数据还没有参与比较。

• if(target

class Solution {
public:
    int search(vector& nums, int target) {
        if(targetnums[nums.size()-1])
        {
            return -1;
        }
        else
        {
            int left=0;
            int right=nums.size()-1;
            while(left<=right)
            {
                int mid=(left+right)/2;
                if(targetnums[mid])
                {
                    left=mid+1;
                }
                else
                {
                    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
26
27
28
29
30
31

二、变式一：元素可以重复

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

1.思路

该变式没有完全改变有序的特性，依然是进行查找，因此还是可以使用二分查找的。

• 还是进行分类讨论，即先处理在数组之外的情况。

• 再在数组内部进行二分查找寻找左右边界。

  寻找边界的关键在于，当每一次比较后的left和right如何进行处理。

  这里以左边界为例：

  当target

  当target>nums[mid]的时候，显然无论元素是否有重复mid的左边都没有target值，因此left=mid+1；

  当target=nums[mid]的时候，由于是寻找左边界，因此不关心mid右边是否有重复的值，但是左边依然有可能有重复的值，因此right=mid-1。

  而最终while循环终止的时候，一定是right=left-1，所以right+1即left，就是左边界。

2.具体实现

class Solution {
public:
    int FindLeftBorder(vector& nums,int target,int left,int right)
    {
        while(left<=right)
        {
            int mid=(right+left)/2;
            if(target>nums[mid])
            {
                left=mid+1;
            }
            else
            {
                right=mid-1;
            }
        }
        if(nums[right+1]==target)
        {
            return right+1;
        }
        else
        {
            return -1;
        }
    }
    int FindRightBorder(vector& nums,int target,int left,int right)
    {
        while(left<=right)
        {
            int mid=(right+left)/2;
            if(target searchRange(vector& nums, int target) {
        vector v;
        v.resize(2);
        if(nums.size()==0)
        {
            v[0]=-1;
            v[1]=-1;
            return v;
        }
        if(target=nums[0]&&target<=nums[nums.size()-1])
        {
            int left=0;
            int right=nums.size()-1;
            int rightborder=FindRightBorder(nums,target,left,right);
            int leftborder=FindLeftBorder(nums,target,left,right);
            v[0]=leftborder;
            v[1]=rightborder;
            return v;
        }
        else
        {
            v[0]=-1;
            v[1]=-1;
            return v;
        }
    }
};
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

3.思考

关键点就在于二分查找的最后结果是落在left=right的情况下，查找边界与简单的二分查找的区别就在于如何处理target=nums[mid]使得当最终left=right的时候，left或者right是一个边界。显然每一次都是对mid+1或者-1操作来缩小查找范围，可以从这里进行思考怎么处理。

三、变式二：非数组二分查找

69. x 的平方根

1.思路

思路主要在于，怎么识别它是一个二分查找。其实还是满足以上两个条件，即无重复元素，数组有序。

求x的平方根，即在x之前的数据中寻找x的平方根。

2.实现

class Solution {
public:
    int mySqrt(int x) {
        int left=1;
        int right=x;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(mid<(x/mid))
            {
                if(mid+1>(x/(mid+1)))
                {
                    return mid;
                }
                left=mid+1;
            }
            else if(mid>(x/mid))
            {
                if((mid-1)<(x/(mid-1)))
                {
                    return mid-1;
                }
                right=mid-1;
            }
            else
            {
                return mid;
            }
        }
        return 0;
    }
};
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
32

注意，这里要使用除法而不能是乘法，有可能出现越界的情况。同时为了避免越界，使用的是left+(right-left)/2的方式来寻找mid。

四、小结

识别二分查找：元素有序，进行查找

处理二分查找：明确结束循环的两种方式，即找到了或者left=right+1等去情况，查找元素使用前者，查找边界使用后者。

思考：通过处理当target=nums[mid]的时候的left和right值来进行切入。

本文将持续更新

，使用的是left+(right-left)/2的方式来寻找mid。

四、小结

识别二分查找：元素有序，进行查找

处理二分查找：明确结束循环的两种方式，即找到了或者left=right+1等去情况，查找元素使用前者，查找边界使用后者。

思考：通过处理当target=nums[mid]的时候的left和right值来进行切入。

本文将持续更新