[LEETCODE] 34. Find First and Last Position of Element in Sorted Array

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1, -1};
        
        int left  = 0;
        int right = nums.size() - 1;
        
        while(left < right){
            int chk = nums[(left + right)/2];
            if(chk == target) {
                left = (left + right)/2;
                right = left;
                break;
            }
            
            if(chk > target){
                right = (left + right)/2 - 1;
            } else {
                left = (left + right)/2 + 1;
            }
        }
        
        // cout<<"left : "<<left<<endl;
        // cout<<"right : "<<right<<endl;
        
        if(left != right) return {-1, -1};
        if(nums[left] != target) return {-1, -1};
        
        int base = left;
        
        while(left > -1 && nums[left] == nums[base]){
            left--;
        }
        while(right < nums.size() && nums[right] == nums[base]){
            right++;
        }
        
        return {left + 1, right - 1};
        
    }
};

시간복잡도 O(logn)으로 풀어달란 조건이 있어 당연히 바이너리 서치로 구현해보았다.

매번 채점할때마다 속도가 좀 다르긴하지만 100%짜리도 나왔다. 

 

 

Discuss를 확인해보니 기억에서 사라졌던 lower_bound, upper_bound를 사용하여

바이너리 서치를 좀 더 쉽게 구현해둔 소스가 있던데 아래와 같습니다.

나중에 요 STL 요긴하게 써먹을 일이 있을 것 같습니다 ㅎ

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0 || nums[nums.size()-1]<target) return {-1, -1};
        
        auto lower = lower_bound(nums.begin(), nums.end(), target);
        auto upper = upper_bound(nums.begin(), nums.end(), target);
        
        if(nums[lower - nums.begin()] != target) return {-1, -1};
        
        // return {lower - nums.begin(), upper - nums.begin()};
        vector<int>result;
        result.push_back(lower-nums.begin());
        result.push_back(upper-nums.begin()-1);
        
        return result;
        
    }
};