代码随想录-二分查找题目分析

二分查找

条件：1.有序 2.元素不重复
二分法最终返回的序号：若元素在列表中则返回该元素位置
若元素不在列表，则返回该元素应该在列表中的顺序

1、给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，确定返回它将会被按顺序插入的位置。

最开始思路是这样的，但如果目标值不存在于数组中，不好确定返回它将会被按顺序插入的位置。

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

参考答案如下，可以看到把middle的计算了放到while循环的第一句，以下面数组举例判断两个方法的优劣：

0 1 2 3 4
0 2 3 5 7
target=6
按照我的思路：
在最后l=r=4,t=6<7,所以r=m-1=3,这个时候还会计算middle=（4+3）/2，这个时候计算的middle是没有意义的，
而按照答案的思路，当二分法每次改变左右边界时，middle值会留到下一次计算，也就是只有left<=right通过时才会计算middle值，并且如果所找的元素不在列表，若target=6<nums[middle]，则r=middle-1，此时需要返回的值(即插入的位置)是middle 或 right+1 或 Letf，若target=8>nums[middle]，则l=middle+1，此时需要返回的值是middle+1 或 right+1 或 Letf,因此最终的返回值可以是 right+1 或 Letf,且答案的方法更严谨简洁。
若target=8
最后l=m+1=5,

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
        return right + 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

2、给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
这道题是二分法的变体，区别在于要利用二分法的性质找得到重复元素的边界，最坏的情况是所有元素都相等。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=getLeftBorder(nums,target);
        int right=getRightBorder(nums,target);
        return {left,right};
    }
private:
     int getRightBorder(vector<int>& nums, int target)  {
         int size=nums.size()-1;
         int left=0,right=size;
         int midlle;
         while(left<=right){
             midlle=(left+right)/2;
             if(target>nums[midlle])    left=midlle+1;
             else if(target<nums[midlle])   right=midlle-1;
             else{
                 if(midlle==size||nums[midlle+1]!=nums[midlle])  return midlle;
                 else  left=midlle+1;
             }
         }
         return -1;
     }

     int getLeftBorder(vector<int>& nums, int target)  {
         int size=nums.size()-1;
         int left=0,right=size;
         int midlle;
         while(left<=right){
             midlle=(left+right)/2;
             if(target>nums[midlle])  {
                 left=midlle+1;
                 }
             else if(target<nums[midlle])   {
                 right=midlle-1;
                 }
             else{
                 if(midlle==0 || nums[midlle-1]!=nums[midlle])  return midlle;     //只有midlle值等于0,即找的数在数组最左边，或者数组前一个数与他不相等，才能判定该数就是左边界
                 else  right=midlle-1;   //否则就将right设置为midlle-1，也就是在找到的
                 //元素不是左边界，则他的左边还有相同元素，则搜索范围变为[left，middle-1]，
                 //此后再进行循环，就能利用二分法每次搜索减少一半区间的性质，并配合上面
                 //的if条件找到左边界，能通过这样找到边界的关键就在于只有在边界位置的元
                 //素值才能通过上面if条件跳出循环并返回自己位置
             }
         }
         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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

//整体区域左闭右开，将二分法等号条件下的处理改变，即可处理这道题
1.整体区域使用左闭右开
2.get_leftBorder取左边界则arget=nums[mid]时不直接返回mid，因为此时mid不一定是边界，而是令right=mid(此处因为是右开区间，
所以直接等于mid，而不是mid-1)，最终得到的left就是左边界，而取右边界时，最终得到的right-1才是右边界因为整体范围是左闭右开，所以要减一。
3.判断target是否存在在Nums中即在若right>=left.。注意这里的right是二分法求解最后得到的right减一的，也就是这里是[left,right]。
class Solution {
public:
     int get_leftBorder(vector<int>& nums, int target){
         int left=0,right=nums.size();//区间左闭右开
         while(left<right){
             int mid=left+(right-left)/2;
             if(target>nums[mid])
                left=mid+1;
            else   //target<=nums[mid]的操作均为移动right，即在mid左边区间继续寻找，这也刚好符合寻找左边界的目的。
                right=mid;
         }
         return left; //最后的left即为右边界
     }
     int get_rightBorder(vector<int>& nums, int target){
         int left=0,right=nums.size();
         while(left<right){
             int mid=left+(right-left)/2;
             if(target>=nums[mid])
                left=mid+1;
            else
                right=mid;
         }
         return right-1;
     }
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=get_leftBorder(nums,target);
        int right=get_rightBorder(nums,target);

        if(right>=left)
            return {left,right};
        else
            return {-1,-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
32
33
34
35
36
37
38
39

3.X的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

这道题是二分法的变题，寻找x平方根整数部分的实际上就是在【1，x】这一区间内寻找数target，满足target的平方小于等于x，target+1的平方大于x。利用二分法寻找target可以让时间效率为O(logn)。
这道题要注意的地方是：
1.x=0的情况要单独处理，因为此时计算的middle也等于0,无法进行下面的除法运算。
2.计算middle时不能直接middle=（left+right）/2，因为（left+right）会有溢出风险，，下面计算target平方同理，要改成除法。

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        int left=1,right=x;
        int middle;
        while(left<=right){  
            middle=left+(right-left)/2;
            if(middle<=x/middle){   //当middle的平方<=x时，要检验target+1的平方是否大于x，
                if((middle+1)>x/(middle+1)) return middle;	如果不满足，说明寻找的区间在middle右边，
            left=middle+1;       则左边界要右移，即 left=middle+1;
            }else{
                right=middle-1;
            }
        }
        return 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.有效的完全平方数
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。

这道题需要注意的是不能采用上一道题中middle<=x/middle的乘法变除法来防止溢出，因为若num=5，当middle=2，middle的平方等于4，应该是小于5的，而用num/middle等于5/2=2=middle，会误判为middle的平方等于5.
这里的方法是定义一个long类型的变量来存储middle的平方

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left=0,right=num-1;
        int middle;
        long square;
        if(num==1)  return true;
        while(left<=right)  {
            middle=left+(right-left)/2;
            square=(long)middle*middle;
            if(square<num) left=middle+1;
            else if(square>num)  right=middle-1;
            else    return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17