33. Search in Rotated Sorted Array

문제 링크: https://leetcode.com/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150

문제

정수 배열 nums 안에 target과 값이 같은 index를 반환하자. 만약 없다면 -1 반환

• O(log n)의 시간복잡도
• 정수 배열 nums의 요소는 중복 존재 X
• 정수 배열 nums는 정렬되어 있지만, 임의의 정수 k번 만큼 회전한 상태이다
  • [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2] (k: 3)

입력

• 오름차순으로 정렬된 정수 배열 nums
• 정수 target

출력

• 정수 배열 (정렬 상관 X)

---

나의 풀이

접근

사실 정렬된 배열이 반으로 분할 후, 다시 붙인 배열을 탐색하는 거라, 반 반 따로 정렬이 되어 있으므로, 간단한 조건문 여러 개로 구현이 될거라 생각했다.

그래서 조건을 계속 쪼개기 시작했지만 조건은 너무 끝도 없어 이 방법이 아니라 생각했다.

시도

class Solution {
    public int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        int mid = (start + mid) / 2;

        while (start <= end) {
            if (nums[mid] == target)
                return mid;
            if (start <= end) {
                if (nums[mid] < target) {
                    start = mid + 1;
                }
                else {
                    end = mid - 1;
                }
            }
            else {
                if (nums[mid] > nums[end]) {
                    if (target > nums[start])
                        end = mid - 1;
                    else
                        start = mid + 1;
                }
                else {
                    if (target > nums[end])
                        end = mid - 1;
                    else
                        start = mid + 1;
                }
            }
        }

        return -1;
    }
}

---

다른 풀이

일단, 다른 풀이의 핵심은 rotate 돌기 전의 오름차순으로 정렬되어 있던 배열의 첫 번째 요소가 현재 어디에 있는 지 먼저 찾고, target과 값이 같은 요소를 탐색한 후, 그걸 이용한다.

똑같이 binary search를 이용해, 가장 작은 값을 탐색하기 때문에, 두 번의 binary search가 실행되지만, 실행 시간은 O(logn)에서 바뀌지 않는다.

public int search(int[] nums, int target) {
    int minIdx = findMinIdx(nums);
    if (target == nums[minIdx]) return minIdx;
    int m = nums.length;
    int start = (target <= nums[m - 1]) ? minIdx : 0;
    int end = (target > nums[m - 1]) ? minIdx : m - 1;
    
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid;
        else if (target > nums[mid]) start = mid + 1;
        else end = mid - 1;
    }
    return -1;
}

public int findMinIdx(int[] nums) {
    int start = 0, end = nums.length - 1;
    while (start < end) {
        int mid = start + (end -  start) / 2;
        if (nums[mid] > nums[end]) start = mid + 1;
        else end = mid;
    }
	return start;
}

• 먼저, 가장 작은 값 (rotate 돌기 전 제일 처음에 있던 요소)을 찾기 위해 findMinIdx() 함수를 실행 후 minIdx 반환
• 만약 target의 값과 가장 오른쪽 끝 요소의 크기 비교에 따라 start와 end 설정
• 이진탐색 진행
  

한 번의 반복문으로 꼭 끝낼 필요는 없다는 걸 명심해야겠다. 사실 2logn 이나 logn이나 시간복잡도는 O(logn)이기 때문이다.