153. Find Minimum in Rotated Sorted Array

문제링크: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

오름차순으로 rotate 되어있는 배열의 가장 작은 수를 반환하는 문제이다.

Solution

Binary search

정렬되있는 데이터기 때문에 이진탐색을 통해 원하는 조건의 수를 찾을 수 있다.
중간값을 이용해 가장 작은 숫자가 존재하는 구간을 점점 좁혀가며 탐색, O(logn)의 시간복잡도를 가진다.

Algorithm

• 배열의 양 끝 Index를 start 와 end로 정의한다.
• 반복문을 돌며 가운데 Index인 mid를 구한다.
• start - mid - end로 구성되있는 구간 start < mid < end < start 중에 증가하지 않는 구간에 가장 작은 숫자가 있으므로 start 와 end의 구간을 반으로 줄일 수 있다.
• 위의 부호가 적용되지 않는 구간에서 다시 반복하고 start = end인 경우 최솟값의 인덱스가 된다.

var findMin = function(nums) {
  let start = 0;
  let end = nums.length - 1;
  
  while (start !== end) {
    const mid = parseInt((start + end) / 2);
    if (nums[start] > nums[mid]) {
      end = mid;
    } else {
      if (nums[mid] > nums[end]) {
        start = mid + 1;
      } else {
        return nums[start];
      }
    }
  }
  
  return nums[start];
};