力扣刷题练习 七【34. 在排序数组中查找元素的第一个和最后一个位置】-二、尝试实现

思路

• 理解题目：nums从小到大，已经排好顺序；第一个问题：找target在不在？第二个问题：返回target下标的开始和结束。
• 直观：用遍历nums一遍，但是时间复杂度O(n)。题目不让用。pass
• 找一个元素在不在集合里？可以想到哈希法。可是选择什么结构？用数组，还是要遍历nums，只是统计次数；用无序的unordered_set或者map，感觉都不好用，放次数还是放下标？还是得遍历nums，时间复杂度没降低。
• 二分查找：因为nums排好序，可以直接用。如果找到target，逐步缩小区间，就可以确定位置。nice。时间复杂度是O(log n)。

代码实现

测试通过。

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