Binary Search (with JavaScript)

# Binary search

Sorted array에서 특정 값을 찾을 때 사용되는 search algorithm이다.

배열의 모든 값을 처음부터 순회하며 탐색하는 sequential search는 시간 복잡도가 O(n)인데 반해, binary search는 O(logn)이기 때문에 정렬되지 않은 배열을 탐색하는 것이 아니라면 binary search를 사용하는 것이 권장된다.

 

# Process

• array의 중간값과 목표값의 크기를 비교한다.
• 중간값과 목표값이 같다면 해당 값의 index를 반환한다.
• 중간값이 목표값보다 작다면 중간값의 오른쪽 sublist에서 위 동작을 반복한다.
• 중간값이 목표값보다 크다면 중간값의 왼쪽 sublist에서 위 동작을 반복한다.

 

# JavaScript로 구현

Binary search를 구현하는 방법은 2가지로, 재귀함수를 이용하는 방법과 반복문을 이용하는 방법이 있다.

 

1. 재귀함수 이용

function binarySearchRecursive(array, target, start, end) {
    let mid = Math.floor((start + end) / 2);
    if (start > end) return undefined;

    if (array[mid] === target) return mid;
    if (array[mid] < target) {
        return binarySearchRecursive(array, target, mid + 1, end);
    }
    return binarySearchRecursive(array, target, start, mid - 1);
}

2. 반복문 이용

function binarySearchLoop(array, target, start, end) {
    let mid;
    while (start <= end) {
        mid = Math.floor((start + end) / 2);
        if (array[mid] === target) return mid;
        if (array[mid] < target) start = mid + 1;
        else end = mid - 1;
    }
    return undefined;
}

 

그렇다면 두 방법 중 무엇이 더 효율적일까?

다음과 같이 테스트를 진행하였다.

const data = [1, 2, 4, 7, 8, 10, 15, 16, 19];
console.time('By recursive');
binarySearchRecursive(data, 1, 0, data.length - 1);
console.timeEnd('By recursive');
console.time('By loop');
binarySearchLoop(data, 1, 0, data.length - 1);
console.timeEnd('By loop');

그 결과는 다음과 같다.

반복문을 사용한 방법이 3배 가량 더 빠른 것을 알 수 있다.

 

재귀함수를 사용하면 parameter가 전달되는 과정에서 반복적으로 값 복사가 이루어므로 이 때문에 반복문이 더 빠른 것이 아닐까 싶다.