704. 二分查找

Solution {
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public:
    int search(vector<int>& nums, int target) {
        int i=0;
        int j=nums.size()-1;
        while(i<=j){
            int mid=(i+j)/2;
            if(nums[mid]>target){
                j=mid-1;
            }else if(nums[mid]<target){
                i=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
        
    }
};

35. 搜索插入位置

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

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

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
class Solution {
public:
    int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; 
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] > target) 
                right = middle - 1;
            else if (nums[middle] < target)  
                left = middle + 1;
            else { 
                rightBorder = middle;
                left = middle + 1;
            }
        }
        return rightBorder;
    }

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

    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况三
        if (rightBorder>=0&&rightBorder<nums.size()&&leftBorder>=0&&leftBorder<nums.size())
            return {leftBorder , rightBorder };
        // 情况二
        return {-1, -1};
    }
};

69. x 的平方根 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int mySqrt(int x) {
        int j=x;
        int i=0;
        while(i<=j){
            long long mid=(i+j)/2;
            if(mid*mid==x)
                return mid;
            else if(mid*mid>x){
                j=mid-1;
            }else
                i=mid+1;
        }
        return j;
    }
};

367. 有效的完全平方数

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