[ 자바스크립트(JavaScript) ] section07 - 10 - 이분검색

📍 section07 - 10 - 이분검색

이분검색은 시간 복잡도가 O(logN)으로 선형 검색인 O(N)보다 빠른 특징을 가지고 있다. 대량의 데이터를 탐색할 때 효과적인데, 예를 들어 1,000,000개의 데이터에서 특정 값을 찾는다고 가정하면, 반복문을 사용해 선형적으로 탐색하면 최악의 경우 백만번을 돌아야 하지만 이진탐색(binarySearch)을 이용하면 최대 11번까지 돌면 된다. 하지만, 이진탐색은 오름차순 혹은 내림차순으로 정렬되어있어야 찾을 수 있는 전제조건이 있다.

 

1. while문의 범위는 lt<=rt인데, lt와 rt가 같을 때까지 돌고 그 lt가 rt보다 커질 경우는 탐색을 종료한다.
2. mid값을 경신한다.
3. target이 arr[mid]보다 왼쪽에 있을 경우 현재 mid 오른쪽에는 내가 찾으려는 값이 없으므로 다음 rt를 mid-1로 재설정한다.
4. target이 arr[mid]보다 오른쪽에 있을 경우 현재 mid 왼쪽에는 내가 찾으려는 값이 없으므로 lt를 mid+1로 재설정한다.

 

728x90

 

let arr = [23, 87, 65, 12, 57, 32, 99, 81];
let m = 32;

console.log(binarySearch(arr, m));
👉🏽 3

function binarySearch(arr, target){ 
    let lt = 0;
    let rt = arr.length - 1;
    arr.sort((a, b) => a - b);

    while (lt <= rt) {
        let mid = Math.floor((lt + rt) / 2);

        if (arr[mid] === target) return mid + 1;
        else if (arr[mid] > target) rt = mid-1;
        else lt = mid+1;
    }
}