【leetcode】二分搜索题目总结

704. 二分查找

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

278. 第一个错误的版本

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (!isBadVersion(mid)) {
                left =  mid + 1; 
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

977. 有序数组的平方

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        int left = 0, right = len - 1;
        
        vector<int> res(len);
        for (int i = len - 1; i >= 0; --i) {
            int leftVal = nums[left] * nums[left];
            int rightVal = nums[right] * nums[right];
            if (leftVal > rightVal) {
                res[i] = leftVal;
                left++;
            } else {
                res[i] = rightVal;
                right--;
            }
        }
        return res;
    }
};

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            int mid  = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        // 二分没有找到插入的位置, 那么target 一定小于 left, 从left 位置插入既能满足题解。
        return left;
    }
};

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

class Solution {
public:
    int leftBound(vector<int>& nums, int target) {
        int left = 0, 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 if (nums[mid] > target) {
                right = mid - 1; 
            }
        }

        // left越界，则不存在
        if (left >= nums.size()) {
            return -1;
        }
        return nums[left] == target ? left : -1;
    }

    int rightBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid  = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1; 
            }
        }
        // right越界，则不存在
        if (right < 0) {
            return -1;
        }
        return nums[right] == target ? right : -1;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) {
            return vector<int>({-1, -1});
        }
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);
        return vector<int>({left, right});
    }
};