[leetcode][33] Search in Rotated Sorted Array

문제 : https://leetcode.com/problems/search-in-rotated-sorted-array/

---

오름차순으로 정렬된 중복되지 않은 요소들을 가진 배열이 있다. 이 배열을 어떤 인덱스에서 회전시킨다.

예를 들어, [0, 1, 2, 3, 4,5,6,7]은 [4, 5, 6, 7, 0, 1, 2, 3] 가 될 수도 있다. 

회전된 배열이 주어질 때, 이 배열에서 target 값이 어디있는지 인덱스를 찾아라. 없다면 -1을 반환.

단, 시간복잡도는 O(logN) 이어야 한다.

---

이분 탐색으로 풀었다.

 

배열 [4 5 6 7 8 0 1] [5 1 2 3 4]로 예를 들어보자.

중간 인덱스를 기준으로 왼쪽과 오른쪽이 있고 이들이 오름차순인지 내림차순인지 구한다.

이 때, 오름차순과 내림차순은 배열을 모두 탐색하는게 아니고 nums[0], nums[중간], nums[마지막]을 비교한 값이다.

즉, nums[중간]-nums[0]이 0이나 양수인 경우 오름차순, 음수인 경우 왼쪽 배열을 내림차순이라 하고.

nums[마지막]-nums[중간]이 0이나 양수인 경우 오름차순, 음수인 경우 오른쪽 배열을 내림차순이라 한다.

왼쪽	오른쪽	배열	target 위치(< m)	target 위치(> m)
오름차순	오름차순	오름차순	왼쪽	오른쪽
오름차순	내림차순	제일 작은수가 오른쪽에 위치	오른쪽, 왼쪽	오른쪽
내림차순	오름차순	제일 작은수가 중간이나 왼쪽에 위치	왼쪽	왼쪽, 오른쪽
내림차순	내림차순	내림차순	오른쪽	왼쪽

먼저 결과부터 보자면 위와 같다.

1) 왼쪽과 오른쪽 모두 오름차순이면 모든 배열이 오름차순이다.

4) 왼쪽과 오른쪽 모두 내림차순이면 모든 배열이 내림차순이다. (근데 오름차순 배열이 주어지므로 이 경우는 나오지 않는다.)

위 두 가지는 쉽게 구할 수 있다.

 

문제는 두 정렬이 다른 경우인데,

2) 왼쪽이 오름차순, 오른쪽이 내림차순인 경우를 먼저 보자.

예제 배열 중 첫번째 배열이 [4 5 6 7 8 0 1] 이에 해당한다.

이 배열은 제일 작은 수(0)이 중간보다 오른쪽에 위치한다. (= 오름차순 배열의 끝이 오른쪽 배열에 위치한다.)

만약 중간(m) 값 7보다 큰 8을 찾는다고 하면 오른쪽 배열에서만 찾으면 된다. 배열의 끝이 오른쪽 배열에 있기 때문이다. 

7보다 작은 수를 찾는다고 하면 왼쪽, 오른쪽 배열을 모두 탐색해야 한다. 예를 들어, 1을 찾는다고 하면 오른쪽 배열을 탐색해야 하고 5를 찾는다고 하면 왼쪽 배열을 탐색해야 하기 때문이다.

 

이제 3) 왼쪽이 내림차순, 오른쪽이 오름차순인 경우를 보자.

이 경우도 2번과 비슷한데 반대이다.

예제 배열 중 두 번째 배열 [5 1 2 3 4]이 이에 해당한다.

이 배열은 제일 작은 수(1)가 중간보다 왼쪽에 위치한다. (= 오름차순 배열의 끝이 왼쪽 배열에 위치한다.)

만약 중간 값 2 보다 작은 수 1을 찾는다고 하면 이는 왼쪽 배열만 탐색하면 된다.

2보다 큰 값을 찾는다고 하면 3을 찾는 경우 오른쪽, 5를 찾는 경우 왼쪽 배열을 탐색해야 하므로 양쪽 모두 탐색해야 한다.

 

이제 이분 탐색으로 정답이 있을 수 있는 범위를 [0, 배열 크기)로 설정한 뒤 위 규칙으로 범위를 줄여나간다.

만약 탐색 중 배열의 중간 값이 target과 같다면 중간 인덱스를 반환한다.

정답 가능 배열의 크기가 0이 된다면 target이 없다는 뜻이므로 -1을 반환한다.

 

시간복잡도는 O(logN)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/33.%20Search%20in%20Rotated%20Sorted%20Array.cpp