이진 탐색 / 이분 탐색(Binary Search)

이진 탐색 알고리즘은 데이터가 정렬된 배열에서 특정한 값을 찾아내는 알고리즘이다.

배열의 중간 값을 선택해 찾고자 하는 값 X와 비교한다.
이때 X가 중간값보다 작으면 중간값을 기준으로 좌측의 데이터들을,
X가 중간값보다 크면 중간값을 기준으로 우측의 데이터들을 대상으로 다시 탐색한다.

위의 과정을 찾고자 하는 값을 찾을때 까지 반복한다.

위 그림처럼 매번 순회 검색을 완료할때마다 검색 대상 데이터가 절반씩 줄어들기 때문에, 순차적으로 찾는 방식보다 훨씬 효율적이다.

시간 복잡도 O(logN)

이진 탐색 구현 in JavaScript

이진 탐색 구현시 정렬된 배열과 start, end, mid 세 변수가 필요하다.

start는 왼쪽 끝 인덱스(탐색 시작 인덱스), end는 오른쪽 끝 인덱스(탐색 종료 인덱스)를 의미한다.
start ~ end 까지가 탐색 범위가 된다.

mid는 start와 end의 중간 지점 인덱스를 의미한다.

start부터 end까지 탐색하는데, 찾고자 하는 값(x)과 현재 중간값(mid)을 비교한다.

• 중간 값(arr[mid])보다 찾고자 하는값(x)이 작다면, 중간 값보다 큰 수는 더이상 탐색 범위에 해당하지 않기에 end의 값을 mid - 1로 해준다.
• 중간 값(arr[mid])보다 찾고자 하는값(x)이 크다면, 중간 값보다 작은 수는 더이상 탐색 범위에 해당하지 않기에 start 값을 mid + 1로 해준다.

위의 로직을 반복하며, 만약 중간값과 찾고자하는 값이 일치하면 true를 반환해준다.
끝까지 찾지 못하면 배열에 찾고자 하는 값이 없는 것이므로 false를 반환한다.

function binarySearch(arr, x) {
  
    let start=0, end=arr.length-1;
         
    // Iterate while start not meets end
    while (start<=end){
 
        // Find the mid index
        let mid=Math.floor((start + end)/2);
  
        // If element is present at mid, return True
        if (arr[mid]===x) return true;
 
        // Else look in left or right half accordingly
        else if (arr[mid] < x)
             start = mid + 1;
        else
             end = mid - 1;
    }
  
    return false;
}

const sample = [1,2,3,4,5,6,7,8,9,10];
sample.sort((a,b) => a-b);
console.log(binarySearch(sample, 5));

참고 자료

• https://www.geeksforgeeks.org/binary-search-in-javascript/
• https://webruden.tistory.com/1046
• https://gurtn.tistory.com/94