Repository navigation
이진 탐색(Binary Search) 알고리즘 정리 #5
Description
개념
정렬된 데이터가 있을 때 특정 값을 효율적으로 찾을 수 있는 알고리즘이다. 가운데 값을 기준으로 오른쪽, 왼쪽 각각의 값보다 큰지 작은지를 파악하여 해당 범위의 중앙값을 선택하여 반복하는 과정을 수행하면 원하는 값을 찾을 수 있다.
구현
function binarySearch(target, array) {
let start = 0;
let end = array.length - 1;
while (start <= end) {
let mid = Math.floor((end + start) / 2);
const guess = array[mid];
if (guess === target) {
return guess;
}
if (guess > target) {
end = mid - 1;
continue;
}
start = mid + 1;
}
return undefined;
}시간복잡도
O(logN)
Activity
voidmatcha commentedon Mar 9, 2021
https://www.acmicpc.net/problem/2343