https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
배열에서 최소값을 찾아야하는데,
이걸 logn안에 풀어보라는 것이다.
만약에 Math.min(...nums)를 하면 O(n)의 시간복잡도를 갖게된다.
그런데 O(logn)이 되려면, 대놓고 이진탐색을 하라는 문제라는 것이다.
근데 웃긴건
예?? ㅋㅋㅋㅋ 0ms.
그래도 의도대로 풀어야하니까
이진 탐색을 구현하는 방법에 대해서 좀 공부해보았다.
예를들어
어떤 단어X를 찾기 위해, 어떤 페이지를 펼쳐보았다.
그 A페이지에서 a라는 단어가 보인다면
그 페이지 이후의 B페이지 펼칠것이다.
B페이지에서 b가 나온다면,
A와 B 사이의 어딘가를 펼칠것이다.
이렇게 반복을 하면서 탐색 범위를 좁혀나간다.
그러다가 X를 만나게 된다.
영어 사전에서 이렇게 찾을 수 있는 이유는 단어가 알파벳 순으로 정렬이 되어있기 때문이다.
즉. 이진탐색은 정렬된 자료구조에서 사용이 가능한 알고리즘이다.
정렬된 데이터에서는 선형탐색보다 성능이 월등히 좋다.
현재 값보다 찾으려는 값이 크다면,
남아있는 데이터에서 현재 위치의 자료를 포함한 이 전 값들을 버린다.
그리고 현재 값을, 남은 데이터의 중간 값으로 초기화.
현재 값보다 찾으려는 값이 더 작다면
남아있는 데이터에서 현재 위치의 자료를 포함한 이후 값들을 버린다.
그리고 현재 값을, 남은 데이터의 중간 값으로 초기화.
이런 알고리즘이다.
이런식으로 현재 값을 초기화해 나가다가, 원하는 값을 얻어낼 수 있다.
이제 어떤 방식으로 구현해볼지 생각해보자.
우선 탈출조건은, 현재 값이 타겟과 같아지는 시점이다.
그리고 현재 자료를 담고 있는 배열은 계속 새로운 배열로 초기화되는 것이, delete를 하는 것보다
시간 복잡도를 맞추기 쉬울 것이다.
아, 근데 중요한건..
이 문제는 타겟이 즉 찾아야 하는 값이 불분명하다. ;;
그리고 이건 무엇보다, 정렬된 데이터에서 값을 찾는게 아니라, 회전한 데이터에서 제일 작은 값을 찾는 문제라는 것을 기억해야한다.
그렇게 때문에, left, right를 각각 0, nums.length -1 로 두어서, left와 right가 같아질때 탈출하고, 그 같아진 index에 대한 nums[index]를 찾아내면 될 것 같다.
더 작은 값이 존재하는지 계속 파악하는 것.으로 생각해야한다.
function findMin(nums) {
let left = 0;
let right = nums.length - 1;
while (left !== right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) {
// 최소값은 오른쪽에 있다
left = mid + 1;
} else {
// 최소값은 왼쪽 구간에 있다 (mid도 포함 가능)
right = mid;
}
}
return nums[left]; // 또는 nums[right]도 같음
}
시간복잡도 : 이진탐색을 썼으므로 O(logn)
공간복잡도 : O(1)
