배열안에 최소값을 찾는 문제 시간복잡도 O(log n)으로 해결해야함
루프마다 루프횟수가 절반으로 줄어들 수 있는 이진탐색(Binary Search)를 대입시켜야함
업앤다운 게임이 생각이 난다
길이만큼 루프를 실행하는 것이 아니라, 조건을 찾을때까지 실행하는 방법
var findMin = function(nums) {
let l = 0;
let r = nums.length -1;
while (l < r) {
let m = Math.floor((l + r) / 2);
console.log("left:" + l + " middle:" + m + " right:" + r);
if (nums[m] < nums[r]) {
r = m;
console.log("r = m edited:" + r);
} else if (nums[m] > nums[r]) {
l = m + 1;
console.log("m + 1 edited:" + l);
} else if (nums[m] < nums[l]) {
r = r - 1;
console.log("r -1 edited:" + r);
}
}
return nums[l];
};
[3,4,5,1,2]
left:0 middle:2 right:4
m + 1 edited:3
left:3 middle:3 right:4
r = m edited:3[4,5,6,7,0,1,2]
left:0 middle:3 right:6
m + 1 edited:4
left:4 middle:5 right:6
r = m edited:5
left:4 middle:4 right:5
r = m edited:4[11,13,15,17]
left:0 middle:1 right:3
r = m edited:1
left:0 middle:0 right:1
r = m edited:0