二分查找

二分查找模板题：704. 二分查找
二分查找前提：

• 有序数组
• 数组中无重复元素

左闭右闭：

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

左闭右开

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

时间复杂度：$O(logn)$
空间复杂度：$O(1)$
二分查找拓展题：
【1】35.搜索插入位置

有两种情况考虑：

1. 在数组中：二分查找
2. 不在数组中：

• 所有数之前
• 在某两数之间
• 在所有数之后

而不在数组中即在二分查找的基础上改变退出循环后返回的值
二分查找退出循环时，左闭右闭left=right+1，左闭右开left=right

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

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

【2】69. x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        int left = 0; int right = x;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long long)mid * mid > x) right = mid - 1;
            else if ((long long)mid * mid < x) left = mid + 1;
            else return mid;
        }
        return right;
    }
};

【3】367. 有效的完全平方数

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0; 
        int right = num;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long long)mid * mid > num) right = mid - 1;
            else if ((long long)mid * mid < num) left = mid + 1;
            else return true;
        }
        return false;
    } 
};

【4】34. 在排序数组中查找元素的第一个和最后一个位置
两次二分，定义新变量first、last

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

【5】74. 搜索二维矩阵
二维转一维

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0;
        int right = m * n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int x = matrix[mid / n][mid % n];
            if (x > target) right = mid - 1;
            else if (x < target) left = mid + 1;
            else return true;
        }
        return false;
    }
};

【6】33. 搜索旋转排序数组
通过二分找到旋转点，在区间内部二分找到目标值

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

【7】153. 寻找旋转排序数组中的最小值

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