Leetcode刷题---34

题目： 给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。
输入： nums = [5,7,7,8,8,10], target = 8
输出： [3,4]
方法一： 二分查找

class Solution {
public:
    int binarySearch(vector& nums, int target, bool lower){
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >=target)){
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    vector searchRange(vector& nums, int target){
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target &&nums  [rightIdx] == target){
            return vector{leftIdx, rightIdx};
        }
        return vector{-1, -1};
    }
};

复杂度分析
时间复杂度： O(logn),n为数组的长度，二分查找的复杂度为O(logn)
空间复杂度： O(1),只需要常数空间存放若干变量

方法二： 二分查找

class Solution {
public:
    // 主函数
    vector searchRange(vector &nums, int target){
        if (nums.empty()) return vector {-1, -1};
        int lower = lower_bound(nums, target);
        int upper = upper_bound(nums, target) - 1;   // 这里需要减 1 位
        if (lower == nums.size() || nums[lower] != target) {
            return vector {-1, -1};
        }
        return vector{lower, upper};
    }
    // 辅函数
    int lower_bound(vector& nums, int target){
        int l = 0, r = nums.size(), mid;
        while (l < r){
            mid = (l + r) / 2;
            if (nums[mid] >= target){
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
    // 辅函数
    int upper_bound(vector& nums, int target){
        int l = 0, r = nums.size(), mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (nums[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};