[Leet Code] 034. Find First and Last Position of Element in Sorted Array

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Find First and Last Position of Element in Sorted Array - LeetCode

 

Solution 1: 반복문의 조건문에서 target값을 찾은 코드

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0) return vector<int>({-1,-1});

        int start = 0;
        int end = nums.size()-1;
        int middle = (start+end)/2;
        
        while(nums[middle]!=target){
            if(target < nums[middle])
            {
                start = start;
                end = middle-1;
                middle = (start+end)/2;
                
                if(start<0 || nums.size()-1 < end || nums.size()-1 < start || end<0 ) 
                	return vector<int>({-1,-1});
                if(target < nums[start] || nums[end] < target) 
                	return vector<int>({-1,-1});
                if(end-start+1==2 &&  (nums[start] < target && target<nums[end]) ) 
                	return vector<int>({-1,-1});
            }
            else if(nums[middle] < target)
            {
                start = middle+1;
                end = end;
                middle = (start+end)/2;
                if(start<0 || nums.size()-1 < end || nums.size()-1 < start || end<0 )
                	return vector<int>({-1,-1});
                if(target < nums[start] || nums[end] < target)
                	return vector<int>({-1,-1});
                if(end-start+1==2 && (nums[start] < target && target<nums[end]) )
                	return vector<int>({-1,-1});
            }
        }
        
        vector<int> result;
        for(int i=start; i<nums.size(); ++i)
        {
            if(nums[i] != target) continue;
            result.push_back(i); 
        }
        if(result.size()==1) result.push_back(result[0]);
        return vector<int>({result[0],result[result.size()-1]});
    }
};

Refactoring

OverFlow를 항상 염두해두고 코드를 작성하자.

안전한 방법Middle = Start + (End - Start)/2

위험  Middle = (Start+End)/2

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0) return vector<int>{-1,-1};

        int start = 0;
        int end = nums.size()-1;
        int middle = start + (end-start)/2;
        
        while(nums[middle]!=target){
            // 0 <= start, start < nums.size(), 0<=end, end < nums.size()
            if(start<0 || nums.size()-1 < end || nums.size()-1 < start || end<0 )
            	return vector<int>({-1,-1});
            // nums[start] <= target, target <= nums[end]
            if(target < nums[start] || nums[end] < target)
            	return vector<int>({-1,-1});
            if(end-start+1==2 &&  (nums[start] < target && target<nums[end]) )
            	return vector<int>({-1,-1});

            if(target < nums[middle])
            {
                start = start;
                end = middle-1;
            }
            else if(nums[middle] < target)
            {
                start = middle+1;
                end = end;
            }
                middle = (start+end)/2;
        }
        
        vector<int> result;
        for(int i=start; i<nums.size(); ++i)
        {
            if(nums[i] != target) continue;
            result.push_back(i); 
        }
        if(result.size()==1) result.push_back(result[0]);
        return vector<int>{result[0],result[result.size()-1]};
    }
};

 

Solution2: 반복문 조건문에서 Left와 Right만 비교하고

 

이렇게 할 때 코드가 훨씬 더 깔끔하게 나왔다. Target값은 반복문 내에서 찾아 검증한다.

이때 bool isFirst를 이용하여 왼쪽으로 더 훑을지 오른쪽으로 더 훑을지 선택한다.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        return { BinarySearch(nums, target, true) , BinarySearch(nums, target, false) };
    }

    int BinarySearch(const vector<int>& nums, int target, bool isFirst)
    {
        int left = 0, right = nums.size()-1, mid = -1;
        int result = -1;

        while(left<=right)
        {
            mid = (left+right) / 2;
            if(nums[mid]==target)
            {
                result = mid;
                isFirst? right=mid-1 : left=mid+1;
            }
            
            else if( target < nums[mid] ) right = mid -1;
            else left = mid+1;
        }
        return result;
    }
};