[알고리즘] 이진 탐색 (Binary Search)

이진 탐색 개념

이진 탐색법은 탐색의 대상인 데이터가 오름차순으로 정렬되어 있는 경우에 데이터를 이분화하면서 특정 값을 탐색하는 알고리즘이다.

1. 가운데에 있는 요소를 먼저 탐색한다.
2. 조건이 가운데 요소보다 정렬순서가 빠른지 느린지를 보고, 탐색범위를 좁힌다.
3. 탐색범위를 좁혔으면 다시 한번 가운데를 탐색해본다.
4. 계속 찾을때까지 반복하여 원하는 결과를 찾으면 탐색 종료.

이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다.

종료조건
1. 리스트에서 검색할 값과 같은 요소를 발견한 경우
2. 더 이상 검색할 범위가 없어 검색 실패(검색값이 존재하지 않는 경우)

function findIndexBinary(array, condition) {
    let head = 0;
    let tail = array.length - 1
    // 아래와 같이 배열의 크기가 짝수인 경우에는 3가지 옵션이 있습니다.
    // 1. 반올림 (Round)
    // 2. 올림 (Ceil)
    // 3. 내림 (Floor)
    // 이번에는 내림을 이용하여 구현을 해보겠습니다.
    let centerIndex  = Math.floor((head + tail) / 2) // 2.5
    
    while(array[centerIndex] !== condition) {
        // 찾는 결과가 없을 떄 (infinity loop prevent)
        if(head > tail) return '결과를 찾지 못했습니다.'

        if (array[centerIndex] < condition) {
          head = centerIndex + 1;
          centerIndex = Math.floor((head + tail) / 2)
        } else {
          tail = centerIndex - 1;
          centerIndex = Math.floor((head + tail) / 2)
        }
    }

    return `${centerIndex}번째 요소가 일치`
}


findIndexBinary([1,2,4,5,6,7], 7)

선형 탐색법과 비교했을 때 평균적으로 이진 탐색법이 탐색 속도가 더 빠르다. (첫번째 요소가 탐색대상이면 선형 탐색이 더 빠르다.)

평균적으로 이진 탐색법이 빠르다고 해서 항상 이진 탐색법을 사용하는 것이 좋다는 뜻은 아니다. 데이터의 양과 저장 상황, 정렬 상황에 따라 적절한 알고리즘을 선택해야한다.

이진 탐색법의 시간복잡도는 O(logN)으로 나타낼 수 있다.