Daily LeetCode Challenge - 153. Find Minimum in Rotated Sorted Array

Problem From.
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

오늘 문제는 원래 정렬되어있는 배열에서 임의의 숫자만큼 옆으로 옮겨진 배열이 주어질때 배열에서 최소의 수를 O(logN) 의 시간복잡도 안에 찾는 문제였다.

이를 위해서는 binary Search 를 이용해야했는데, 원래 binary Search 는 정렬된 배열에서 사용하는것이 정석이나, 이 문제에서는 옆으로 임의의 수만큼 옮겨져있어서 조금 수정해야할 부분이 있었다.

먼저 가장 중요한 부분은, nums[start] 가 nums[end] 보다 작다면, 이미 정렬되어있다는 뜻이므로 start 의 원소를 반환하면 되었다. 만약 그렇지 않다면 binary search 를 사용해야했는데, nums[mid] 보다 start 가 작다면, 왼쪽은 이미 큰 수들로 정렬되어있다는 뜻이므로, 우리는 오른쪽을 탐색해야 하므로 start 를 mid +1 로 바꾸어준다. 그렇지 않다면 우리는 왼쪽을 탐색해야한다는 뜻이므로 end 를 mid-1 로 바꾸어준다. 위의 과정을 반복하다보면 정답을 얻을 수 있었다.

class Solution {
    fun findMin(nums: IntArray): Int {

        var answer = nums[0]
        var start = 0
        var end = nums.size - 1

        while (start <= end) {
            if(nums[start] < nums[end]) {
                answer = Math.min(answer, nums[start])
            }

            val mid = (start + end) / 2
            answer = Math.min(answer, nums[mid])

            if(nums[mid] >= nums[start]) start = mid + 1
            else end = mid - 1

        }

        return answer

    }
}