📌 Toy coplit - 해당하는 알고리즘이 있는지 구글링 먼저 해보기!
이진 탐색 알고리즘 검색하고 나무위키만 봤어도 금방 풀었을 문제인데, 혼자 트리 생성하고 메소드 구현하다 시간만 날렸다. 기록해두고 잊지 않아야겠다.
실제로 트리를 구현할 필요는 없다. 개념적으로 BST 구조라는 것이 떠오른다면 해당 알고리즘을 사용하자. 정렬된 리스트에서 빠르게 특정 값을 검색하고자 할 때 사용할 수 있다.
아래 과정을 while
문으로 반복하며 자료의 가운데 항목(mid
)과 target
을 비교한다.
target
과 같으면 바로 리턴target
보다 작으면 mid
기준 오른쪽 배열로 대상 범위를 좁히고 다시 탐색target
보다 크면 mid
기준 왼쪽 배열로 대상 범위를 좁히고 다시 탐색단순 탐색에 비해 매우 빠르게 데이터를 찾을 수 있지만, 데이터가 반드시 정렬되어 있어야 한다.
탐색 대상의 범위를 1/2로 줄여나가며 반복적으로 탐색한다.
아래의 코드가 전형적인 코드 형식이므로 그대로 활용하면 된다.
const binarySearch = function (arr, target) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let mid = Math.floor((start+end)/2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
end = mid - 1;
} else if (arr[mid] < target) {
start = mid + 1;
}
}
return -1;
};