153. Find Minimum in Rotated Sorted Array

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

Find Minimum in Rotated Sorted Array - LeetCode

---

O(lonN)의 시간 복잡도로 가장 작은 수 찾기

 

내 풀이

- 이진 탐색(인줄 착각함 ㅜㅜ... 내 풀이는 이진 탐색이 아니다...)

1. left, right, mid가 아닌, first, second, third로 변수 선언

2. first, second, third 세 값을 비교하여 minIndex와 maxIndex 찾기

(삼항 연산자를 이용하면 됨.)

3. minIndex와 maxIndex로 부터 midIndex 추출

4. (만약 midIndex === minIndex || midIndex === maxIndex) return nums[minIndex]

5. first = minIndex, second = midIndex, third = maxIndex로 할당

6. 2번 부터 4번이 실행될때까지 반복

 

 

예외 처리를 너무 많이해서 코드가 별로인듯, 최적화 가능한 부분도 보임

var findMin = function(nums) {
     let first = 0, third = nums.length - 1, second = Math.floor((first + third) / 2);

     if(nums.length === 1) return nums[first];
     if(nums.length === 2) return nums[first]>nums[third] ? nums[third] : nums[first];
     if((nums[first] < nums[second]) && (nums[second] < nums[third])) return nums[first];
     if((nums[third] < nums[second]) && (nums[second] <nums[first])) return nums[third];

     while(1) {
         let max = nums[first] > nums[third] ? (nums[first] > nums[second] ? first : second) : (nums[third] > nums[second] ? third : second);
         let min = nums[first] < nums[third] ? (nums[first] < nums[second] ? first : second) : (nums[third] < nums[second] ? third : second);
         let mid = Math.floor((max + min) / 2);

         if(mid === max || mid === min) return nums[min];

         first = min;
         third = max;
         second = mid;
     }
};

---

다른 사람 풀이

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/discuss/403413/Clean-JavaScript-solution

 

오름차순 배열이 회전한다. 이 상태에서 양 끝 L과 R을 잡고, M을 구한다.

이때 M이후의 값들은 오름차순인 경우와 오름차순이 아닌 경우로 나뉜다. 잘 와닿지 않겠지만 이를 캐치해야 이진탐색 방향을 잡을 수 있다.

 

 

function findMin(nums) {
    let l = 0;
    let r = nums.length - 1;
    while (l < r) {
      const m = Math.floor((l + r) / 2);
      if (nums[m] > nums[r]) l = m + 1;
      else r = m;
    }
    return nums[l];
  }