33. Search in Rotated Sorted Array

---

문제 분석

정렬된 배열이 특정 횟수 회전되어 주어진다.
정수 하나가 주어진다.
정렬된 배열에 정수가 존재하면 인덱스를 리턴,
없다면 -1을 리턴

---

풀이 과정

이분 탐색을 응용하는 문제.

원래 배열 nums = [0, 1, 2, 4, 5, 6, 7]

1회전된 배열 = [1, 2, 4, 5, 6, 7, 0]
2회전된 배열 = [2, 4, 5, 6, 7, 0, 1]
3회전된 배열 = [4, 5, 6, 7, 0, 1, 2]

4회전된 배열 = [5, 6, 7, 0, 1, 2, 4]
5회전된 배열 = [6, 7, 0, 1, 2, 4, 5]
6회전된 배열 = [7, 0, 1, 2, 4, 5, 6]

중간 인덱스를 기준으로 좌, 우를 나누고
좌측이 정렬되었는가? 우측이 정렬되었는가? 를 분기점으로 탐색을 시작할 수 있다.

회전된 배열들을 보자면
1,2,3 회전된 배열들은 중간값을 기준으로 좌측이 오름차순 정렬되었다.
4,5,6 회전된 배열들은 중간값을 기준으로 우측이 오름차순 정렬되었다.
(중간값도 포함해서 봐야한다.)

좌측이 정렬되어 있는가? 우측이 정렬되어 있는가? 를 기준으로 주어진 정수 target 과 값을 비교한다.

• 좌측이 정렬되어 있을 때
  midIndex 는 좌측의 정렬된 값들 중 가장 큰 값이다.
  midIndex 보다 target 이 크다면 좌측의 정렬된 값들을 확인할 필요가 없다.

  startIndex 는 가장 작은 값이다.
  startIndex 가 target 보다 작다면 좌측의 정렬된 값들을 확인할 필요가 없다.

• 우측이 정렬되어 있을 때
  midIndex 는 우측의 정렬된 값들 중 가장 작은 값이다.
  midIndex 보다 target 이 작다면 우측의 정렬된 값들을 확인할 필요가 없다.

  endIndex 는 우측의 정렬된 값들 중 가장 큰 값이다.
  endIndex 보다 target 이 크다면 뜻은 우측의 정렬된 값들을 확인할 필요가 없다.

위의 로직을 토대로 인덱스들을 수정해가면 정답을 찾을 수 있다.

---

나의 생각

중간인덱스를 기준으로 좌, 우 어디를 탐색해야 효율적인지는 탐색 조건문을 어떻게 설정하느냐에 따라 달린 것 같다.

---

코드

   public int search(int[] nums, int target) {
        int startIndex = 0;
        int endIndex = nums.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
            if (nums[midIndex] == target) return midIndex;
            
            if (nums[startIndex] <= nums[midIndex]) {
                if (nums[midIndex] < target || nums[startIndex] > target) {
                    startIndex = midIndex + 1;
                } else {
                    endIndex = midIndex - 1;
                }
            } else {
                if (nums[midIndex] > target || nums[endIndex] < target) {
                    endIndex = midIndex - 1;
                } else {
                    startIndex = midIndex + 1;
                }
            }           
        }  

        return -1;
    }