153. Find Minimum in Rotated Sorted Array

---

문제 분석

이미 정렬되어 있는 배열이 특정 횟수 만큼 회전되어 주어질 때 최솟값을 찾는 문제

---

풀이 과정

예제를 기준으로 이분 탐색 로직을 설명한다.
원래 배열은 정렬된 배열이다.

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

1회전 nums = [7, 0, 1, 2, 4, 5, 6]  // 2를 기준으로 6을 비교
2회전 nums = [6, 7, 0, 1, 2, 4, 5]  // 1를 기준으로 5를 비교
3회전 nums = [5, 6, 7, 0, 1, 2, 4]  // 0를 기준으로 4를 비교
4회전 nums = [4, 5, 6, 7, 0, 1, 2]  // 7를 기준으로 2를 비교
5회전 nums = [2, 4, 5, 6, 7, 0, 1]  // 6를 기준으로 1을 비교
6회전 nums = [1, 2, 4, 5, 6, 7, 0]  // 5를 기준으로 0을 비교

정렬된 배열이므로 중간 인덱스 값을 기준으로
시작 인덱스, 마지막 인덱스의 값들을 조건문으로 비교해가며 인덱스들을 수정하면 된다.

만약에 중간 값 < 마지막 값 이 성립한다면 왼쪽 배열에 최솟값이 있다는 뜻

• 마지막 인덱스 를 중간 인덱스 로 바꿔준다.

만약에 중간 값 >= 마지막 값 이 성립한다면 오른쪽 배열에 최솟값이 있다는 뜻

• 시작 인덱스 를 중간 인덱스 + 1 로 바꿔준다.

최솟값을 찾는 문제이기 때문에 중간 값 보다 마지막 값 이 크다면
배열을 절반으로 잘랐을 때 오른쪽을 탐색할 필요가 없다. (정렬되어 있기 때문에)

---

나의 생각

'정렬된' 조건이 성립한다면 충분히 이분 탐색으로 접근할 수 있는 것 같다.

---

코드

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

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

        return nums[startIndex];
    }