[Binary Search] Find Minimum in Rotated Sorted Array

153. Find Minimum in Rotated Sorted Array

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[]} nums
 * @return {number}
 
 * Runtime	: 57 ms
 * Memory	: 43.82 MB
 */
var findMin = function(nums) {
  if(!nums.length) {
    return;
  }
  
  if(nums.length === 1) {
    return nums[0];
  }

  let left = 0;
  let right = nums.length - 1;

  const mid = Math.round((left + right) / 2);

  const divA = findMin(nums.slice(left, mid));
  const divB = findMin(nums.slice(mid));

  return divA > divB ? divB : divA;
};

지난 게시글 [Binary Search] Search Insert Position 에서 중간 인덱스를 구하는 방법 중 하나인 mid = Math.floor((start + end) / 2);은 배열에서 인덱스를 탐색하는 경우에 적절합니다. 라고 언급하였다. 하지만 본 해답에서 Math.round 메소드를 Math.floor로 수정하면 재귀를 탈출하지 못한다.

Example 1의 nums = [3,4,5,1,2];을 예로 함수가 재귀로 호출될 때 넘겨지는 인자의 예상 결과는 다음과 같지만,

[ 3, 4 ] [ 5, 1, 2 ]
[ 3 ] [ 4 ]
[ 5 ] [ 1, 2 ]
[ 1 ] [ 2 ]

Math.floor는 다음과 같다.

[ 3, 4 ] [ 5, 1, 2 ]
[] [ 3, 4 ]
[] [ 3, 4 ]
[] [ 3, 4 ]
[] [ 3, 4 ]...

따라서, 지난 게시글에서 총 숫자에서 특정 숫자를 탐색하는 경우에는 Math.round() 함수를 사용하는 것이 더 적절할 수 있습니다. 라고 언급하였습니다. 이번 게시글을 통해서 배열에서 인덱스를 탐색하는 경우를 포함해 중간 인덱스를 구하는 모든 방법에서 mid = Math.<WHITCH METHOD>((start + end) / 2);은 안정적이라고 할 수 있다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using binary search with loop

해답의 전문은 링크를 확인해주세요.

/**
 * Runtime	: 54 ms
 * Memory	: 42.22 MB
 */
var findMin = function(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    let mid = left + Math.floor((right - left) / 2);

    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return nums[left];
};

필자의 해답과 달리 반복을 사용하였으며, 지난 게시글 [Binary Search] Search Insert Position 에서 중간 인덱스를 구하는 방법 중 하나인 mid = left + (right - left) / 2; 를 사용하였습니다.