[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/

---

내림차순 정렬된 정수 배열과 target 값이 주어지면 배열에서 target 값의 시작 위치와 끝 위치를 찾아라.

만일 target을 찾을 수 없다면 [-1, -1]을 반환해라.

O(log N) 복잡성을 가지는 알고리즘을 작성해라.

---

logN 복잡성이라는거 보니 이분탐색으로 해야겠다.

 

이분탐색을 진행하면서 target 값을 찾는 경우 정답배열의 최소값, 최대값을 갱신한다.

그리고 시작 위치와 끝 위치를 찾아야 하므로 여기서 끝내지 않고 (left, m-1), (m+1, right) 로 이분탐색 2개를 다시 실행시킨다. (m = (left + right)/2)

그런데 이렇게 구현한 경우 target 값이 많은 경우 탐색 범위가 많이 분할되므로 이 경우 비교적 느려질 수 있다.

 

그래서 이분탐색을 총 두 번 탐색하는데 target 값을 찾은 이후 왼쪽 방향으로만 재탐색하게 하면 이는 target 값의 시작 위치를 찾을 것이고 오른쪽 방향으로만 재탐색하게 하면 종료 위치를 찾을 것이다.

 

처음 설명한 방법을 1, 두 번째로 설명한 방법을 2번이라 하겠다.

두 방법 모두 탐색 시작 부터 target 값을 찾는데까지는 동일한 시간이 걸리고 이후부터 방법 차이가 나기 시작한다.

즉, 1번 방법은 찾은 후부터 시간이 오래 걸릴수 있다는 단점이 있고 2번 방법은 target 값을 찾는데까지 로직이 두 번이 실행된다는 단점이 있다. 

 

target 값을 찾는걸 한 번만 수행하게 코딩할수도 있지만 두 번 돌려도 충분한 시간이기 때문에 그냥 두 번 돌렸다.

시간복잡도는 상수 생략해서 O(logN).

---

소스코드 (2번 방법) : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/34.%20Find%20First%20and%20Last%20Position%20of%20Element%20in%20Sorted%20Array.cpp