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

문제

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

Your algorithm's runtime complexity must be in the order of O(log n).

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

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

 

Approach

배열이 정렬되어 있으므로 순서대로 읽으며 target이 발견되면 시작점으로 기록하고

target보다 큰 원소가 나오면 그 바로 전 index를 끝점으로 기록한다.

target이 배열에서 가장 큰 경우까지 따로 처리해줘야함.

이 방법으로는 O(n)만에 풀 수 있다.

 

Optimization

배열을 앞에서부터 순서대로 읽지 않고 binary search 2번으로 시작점과 끝 점을 찾는다.

이론적으론 시간복잡도가 O(ln(n))이 되어 빨라져야 하지만

실제 동작 시간의 차이는 없었다.

 

Code

Linear search

https://github.com/chi3236/algorithm/blob/master/LeetCode_FindFirstAndLastPositionOfElementInSortedArray_Linear.cpp

chi3236/algorithm

Binary serach

https://github.com/chi3236/algorithm/blob/master/LeetCode_FindFirstAndLastPositionOfElementInSortedArray.cpp_BS.cpp

chi3236/algorithm