[LeetCode] Find Minimum in Rotated Sorted Array - Javascript

Find Minimum in Rotated Sorted Array

[특정 값을 기준으로 뒤바뀌어 정렬이 되어 있는 배열의 target 찾기]

제약 조건 

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

 

Example

ex1) Input: nums = [3,4,5,1,2]
     Output: 1
     Explanation: The original array was [1,2,3,4,5] rotated 3 times.

ex2) Input: nums = [4,5,6,7,0,1,2]
     Output: 0
     Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.


ex3) Input: nums = [11,13,15,17]
     Output: 11
     Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

문제 접근 방식

정렬이 되어있지만, 특정 인덱스를 기준으로 돌아간 배열이 주어졌을 때, 최솟값을 구하는 문제이다.

만약 start가 end보다 작거나 같다면 해당 배열은 정렬이 되어있다는 의미로 while 문을 탈출해 nums[start]를 리턴해 정답을 풀이한다.

      if (nums[start] <= nums[end]) {
         break;
      }

 

nums[start]가 nums[mid]보다 작거나 같다면, 배열의 절반 중 왼쪽은 정렬이 되어있다고 봐도 된다.
즉 해당 제어문이 true라면 start를 mid+1로 업데이트하고, 아니라면 end를 mid로 업데이트한다.
해당 제어문을 반복하며 nums[stasrt]가 nums[end]보다 작거나 같을 때까지 즉 배열이 정렬되어 있을 때까지,

start와 end의 값을 초기화한다.

      let mid = Math.floor((start + end) / 2);
      if (nums[start] <= nums[mid]) {
         start = mid + 1;
      } else {
         end = mid;
      }

sovle 코드

var findMin = function (nums) {
   let start = 0,
      end = nums.length - 1;
   while (start <= end) {
      if (nums[start] <= nums[end]) {
         break;
      }
      let mid = Math.floor((start + end) / 2);
      if (nums[start] <= nums[mid]) {
         start = mid + 1;
      } else {
         end = mid;
      }
   }
   return nums[start];
};