[C++] LeetCode : Search for a Range

Question

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

 

오름차순으로 정렬된 정수 배열이 주어지면 주어진 목표 값의 시작 위치와 끝 위치를 찾습니다.
배열에서 target을 찾을 수 없으면 [-1, -1]을 반환합니다.

시간 복잡도가 O(log n)인 알고리즘을 작성해야 합니다.

 

제약사항

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 모든 배열의 요소를 다 봐야할 것 같지만, 이진 탐색을 하면 모든 원소를 다 보진 않아도 된다.

고려사항

• 배열의 원소가 없을 경우
• target값이 배열안에 없을 경우

---

Solution1 (Bruth Force)

순차적으로 Target을 탐색한다. 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start, end;
        start = end = -1;

        for(int i = 0; i<nums.size(); i++){
            if(num == target){
                if(start == -1) {
                    start = end = i;
                }else{
                    end = i;
                }
            }
        }
        
        return {start, end};
    }
};

• Time complexity : O(n) 
• Space Complexity : O(1) 

Solution2 (Binary Search)

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

• Time complexity : O(logN) 
• Space Complexity : O(1) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/802/

Explore - LeetCode