[Algorithm] Binary Search 알고리즘 Javascript (반복, 재귀, 트리구조)

How to Imprement Binary Search Algorithm in Javascript?

 

 

이진(이분) 탐색 Binary Search

 

이진 탐색(Binary Search)란 검색 대상 데이터를 절반씩 나누어 가며 검색하는 방법이다. 데이터를 순차적으로 탐색하는 순차탐색(Linear Search)는 정렬되어 있지 않은 데이터를 검색할 때 유용하지만 시간 복잡도가 O(n)이기 때문에 효율성이 높지 못하다. 

 

이진 탐색을 사용할 경우 데이터를 절반씩 쪼개가며 검색하기 때문에 효율성 면에서 활용도가 높은 편이다. 이진 탐색의 시간 복잡도는 O(LogN)이다.

 

선행조건

이진 탐색을 수행하기 위해서는 선행조건이 필요하다. 먼저 주어진 데이터의 수를 미리 알고 있어야 한다. 배열로 주어진 경우 arr.length 따위의 문법으로 데이터의 길이를 파악하기는 어렵지 않다.

 

두번째 선행조건은 주어진 데이터가 정렬되어 있어야 한다는 것이다. 나눠진 데이터 그룹을 선택하는 기준으로 대소 관계를 사용하기 때문이다. 

 

 

 

이진 탐색 Algorithm

 

① 오름차순으로 정렬된 데이터가 주어진다. 만약 1~9까지의 데이터 중 7을 찾아야 하는 상황을 가정해보자. 정렬된 데이터의 start와 end를 지정한다. 

 

 

② start와 end를 이용해 mid를 구한다. mid 지점은 (start + end) / 2로 구할 수 있다.

 

③ mid와 Target을 비교해서 양분된 영역 중 하나를 선택하게 된다.

만약 Target이 mid 보다 큰 경우 오른쪽에 Target이 위치하게 된다. 이 경우 mid+1 를 start로 지정해서 검색을 진행한다.

 

만약 Target이 mid 보다 작은 경우 왼쪽에 Target이 위치하게 된다. 이 경우 mid-1 를 end로 지정해서 검색을 진행한다.

 

만약 Target이 mid와 같은 경우 탐색이 완료되었기 때문에 mid를 반환후 종료한다.

 

mid에 +1과 -1을 하는 이유는 mid가 이미 검색되었기 때문에 검색 범위를 좁히기 위해서다.

 

④ 만약 start가 end보다 커질 때 까지 Target을 찾지 못하는 경우 -1을 반환한다.

 

 

이진 탐색(Binary Search) 소스코드 Javascript

 

이진 탐색 알고리즘은 start와 end의 순서가 바뀔 때 까지 반복해야 하기 때문에, 일반 반복문 사용하는 경우와 재귀함수를 사용하는 경우로 구분될 수 있다.

 

① 일반 반복문 사용

 

// 이진 탐색 구현

const binarySearch = function (arr, target) {

let startPoint = 0;
let endPoint = arr.length-1;
let midPoint = Math.floor((startPoint+endPoint)/2);

while(startPoint <= endPoint){
    if(target === arr[midPoint]){
        return midPoint;
    }

    if(target > arr[midPoint]){
        startPoint = midPoint+1;
    }

    else if(target < arr[midPoint]){
        endPoint = midPoint-1;
    }
    midPoint = Math.floor((startPoint+endPoint)/2);
}

return -1;
    
}

 

② 재귀 함수 사용

// 이진 탐색 재귀 알고리즘 구현

const binarySearch = function (arr, target) {

let startPoint = 0;
let endPoint = arr.length-1;
let midPoint = Math.floor((startPoint+endPoint)/2);

const recur = (s ,m, e) =>{
    m = Math.floor((s+e)/2);

    if(target === arr[m]) return m;
    if(s > e) return -1; 

    if(target > arr[m]){
        return recur(m+1, m, e);
    }
    else if(target < arr[m]){
        return recur(s, m, m-1);
    }
}

return recur(startPoint ,midPoint ,endPoint);
}

 

 

성능 비교

일반 반복문을 사용해서 트리 탐색을 진행할 경우 시간복잡도는 O(N)이다. 즉 데이터의 길이가 증가하면 증가할 수록, 연산의 횟수또한 정비례 관계로 증가하게 된다. 

 

만약 아래 처럼 순차 탐색을 진행할 경우 많은 연산이 필요하다. 예를 들어 1부터 999까지 배열에서 756을 찾는 경우 757번의 연산이 필요하다.

// 순차 탐색

const LinearSearch = function (arr, target) {
    let result = -1;
    for(let i=0; i<arr.length; i++){
        count++;
        if(arr[i] === target){
            result = i;
            break;
        }
    }
    return result;
}

 

테스트를 위해 0부터 999까지 요소로 채워진 배열을 생성한다.

let tempArr = [...Array(1000).keys()]

let output = binarySearch(tempArr, 756);

console.log(`
    output : ${output},
    count : ${count}

`);

 

반면 위의 이진 탐색을 사용할 경우 시간복잡도는 O(Log N)이기 때문에 연산 횟수는 7번 소요된다! 획기적으로 연산횟수를 줄이면서 탐색이 가능해지는 것이다. 

 

// 순차 탐색
output : 756,
count : 757

// 이진 탐색
output : 756,
count : 7

 

이진 탐색 뿐만 아니라 이진 트리 탐색을 사용할 수도 있다. 이진 트리 탐색 또한 시간 복잡도는 O(Log N)이다. 

// 이진 트리 탐색(Binary Tree Search)

const binarySearch = function (arr, target) {
    class Tree{
        constructor(value){
            this.value = value;
            this.left = null;
            this.right = null;    
        }
        

        insertValue(value){
            if(this.value > value){
                if(this.left === null){
                    this.left = new Tree(value);
                }else{
                    this.left.insertValue(value);
                }
                
            }else if(this.value < value){
                if(this.right === null){
                    this.right = new Tree(value);
                }else{
                    this.right.insertValue(value);
                }
            }
        }

        searchValue(value){
            if(this.value === value){
                return arr.indexOf(value);
            }

            if(this.value > value){
                if(this.left){
                    return this.left.searchValue(value);
                }
                return -1;
            }
            if(this.value < value){
                if(this.right){
                    return this.right.searchValue(value);
                }
                return -1;
            }
        }
    }

    const tree = new Tree(arr[0]);
    arr.forEach((item)=>tree.insertValue(item))
    return tree.searchValue(target);
    }

 

 

이진 탐색 정리

 

만약 정렬된 데이터에서 탐색을 진행할 경우 이진 탐색이 압도적으로 유리한 결과를 가져올 수 있다. 이진 탐색을 이용할 경우 전체 데이터의 길이를 알고 있어야 하고, 정렬된 데이터를 가지고 탐색을 진행해야 한다는 사실을 명심하자.

 

또한 모든 반복문은 재귀 함수로 표현이 가능하다. while문을 사용해도 되지만, 로직이 복잡해지고, 간결한 소스코드를 작성해야 하는 경우 재귀함수가 훨씬 유용하기 때문에 가능하면 반복문으로 표현할 수 있는 로직을 재귀함수로 변경하는 습관을 가지도록 하자.

 

 

 

 

[Algorithm] Javascript Tree 자료구조 구현하기 (소스코드 포함)

 

[Algorithm] Data Structure Tree , 트리 자료구조란? 이진 탐색 트리 (BST, Binary Search Tree)

 

[Algorithm] 분할정복 거듭제곱 분할제곱 알고리즘 Javascript