704. 二分查找

题目链接

状态：一遍过
思路：基本功

35. 搜索插入位置

题目链接
状态：有思路且三遍过
思路：注意是升序，分两种情况：

  1. 数组中有该元素 = 二分查找
  2. 数组中没有该元素 = 查找失败后情况为： $left>right$
    left向右超过right，说明nums[right]<target,right+1=left=n
    right向左超过left，说明位置在开头nums[left ]<target,right+1=left=n

答案思路：考虑所有情况：

// 分别处理如下四种情况
// 目标值在数组所有元素之前 [0, -1]
// 目标值等于数组中某一个元素 return middle;
// 目标值插入数组中的位置 [left, right]，return right + 1
// 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，
所以 return right + 1

暴力解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
        // 分别处理如下三种情况
        // 目标值在数组所有元素之前
        // 目标值等于数组中某一个元素
        // 目标值插入数组中的位置
            if (nums[i] >= target) { // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果
                return i;
            }
        }
        // 目标值在数组所有元素之后的情况
        return nums.size(); // 如果target是最大的，或者 nums为空，则返回nums的长度
    }
};

注意区间范围！！！

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

题目链接
状态：有思路且三遍过
失败原因：输出格式错误和vector语法不熟练
思路：利用二分查找的结构，先找到一个满足条件的点，在以此为基点向前向后去找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        int left=0,right=nums.size()-1,mid;
        vector<int> res(2,-1);
        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]>target) right=mid-1;
            else if(nums[mid]<target) left=mid+1;
            else {
                int start,end;
                start=end=mid;
                while(start>=0&&nums[start]==target) start--;
                while(end<nums.size()&&nums[end]==target) end++;
                res[0]=start+1;res[1]=end-1;
                return res;
            }
        }
        return res;
    }
};

练习思路：
两次二分查找，找到左边界和右边界:
右边界，小等更新左，右边界为左；
左边界，大等更新右，左边界为右。

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};

69. x 的平方根

题目链接
状态： 两遍过
错误原因：使用 $mid*mid>x$ 时运行超时，随即改为 $mid>x/mid$ 成功
思路： 利用二分查找思想

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

367. 有效的完全平方数

题目链接
状态：两遍
错误原因：套用上一题模板，但是未能考虑到当num=5时，mid=2，mid=num/mid但返回为false

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
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left=0,right=num;
        long mid;
        //简单粗暴直接算
        while(left<=right){
            mid=(left+right)/2;
            if(mid*mid>num) right=mid-1;
            else if(mid*mid<num) left=mid+1;
            else return true;
        }
        return false;
    }
	class Solution {

    bool isPerfectSquare1(int num) {
        if(num==1) return true;
        int left=1,right=num/2,mid;
        while(left<=right){
            mid=(left+right)/2;
            if(mid>num/mid) right=mid-1;
            else if(mid<num/mid) left=mid+1;
            else {
            //使用除法避免超时
                if(num%mid==0) return true;
                else return false;
            }
        }
        return false;
    }
};

};