자바스크립트 핵간단한 이진탐색 구현 기본 템플릿

 

정렬된 배열이 있다면, 원하는 타깃 원소 또는 타깃 원소의 인덱스는 이진 탐색으로 찾는 게 시간 복잡도 최악 기준 O(logN)으로 제일 효율성이 좋다. 이진 탐색의 원리는 배열의 가운데 원소를 고르는 것부터 설명된다.

 

const mid = Math.floor((첫 인덱스 + 마지막 인덱스) / 2);

 

첫 인덱스와 마지막 인덱스는 반복문을 통해 계속 바뀌므로 let으로 선언해준다.

 

let left = 0;
let right = arr.length - 1;

 

만약 원하는 타깃 원소가 가운데 원소랑 일치한다면 그 원소의 인덱스를 리턴해준다.

 

if (array[mid] === target) {
    return mid;
}

 

그렇지 않은 경우, 선택했던 가운데 원소가 타깃 원소보다 큰 경우와 작은 경우를 나눠 인덱스 left, right를 그에 따라 바꿔준다. 이렇게 인덱스를 바꿔주면 탐색하는 배열이 한 번 반복문 돌 때마다 절반으로 뚝뚝 나뉘기 때문에 시간 복잡도가 logN인 것이다.

 

구현한 전체 코드는 다음과 같다.

 

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

 

물론 이진 탐색의 원리가 간단한 거랑 별개로, 난이도가 높은 이진 탐색 문제들은 이진 탐색으로 접근해야 하는지조차 감이 안 오는 경우가 좀 있는 듯하다.