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

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

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 이진 탐색

문제 난이도 : Medium

 

문제

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 값의 범위를 구하시오.

target이 없으면 -1, -1을 반환하시오.

 

O(log n)내로 해결하시오.

 

풀이

이진 탐색을 두 번하여 양 끝의 값을 찾으면 된다.

시작 인덱스를 구할 때에는 목표값을 찾았을 때, 우선 현재 인덱스를 저장했다가, right을 mid-1로 해서 범위를 지정하면 더 왼쪽 지점을 탐색한다.

끝 인덱스를 구할 때에는 목표값을 찾았을 때, 우선 현재 인덱스를 저장했다가, left를 mid+1로 해서 범위를 지정하면 더 오른쪽 지점을 탐색한다.

 

코드

C++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        vector<int> result{-1, -1};

        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                result[0] = mid; 
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        left = 0;
        right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                result[1] = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
};