[알고리즘] 이진 탐색 - JavaScript

이진 탐색? 

정렬 되어 있는 요소들을 반씩 제외하면서 찾는 알고리즘

O(log n)만큼의 시간 복잡도가 걸린다. 

 

이진 탐색의 특징

• 반드시 정렬이 되어 있어야 사용이 가능하다. 
• 배열 혹은 이진 트리를 사용하여 구현할 수 있다. 
• O(log n) 시간 복잡도로 상당히 빠르다. 

JavaScript에서 사용하기

const arr = [1, 1, 2, 5, 10, 100, 300, 5000, 120000];

function binarySearch(array, findValue) {
    let left = 0;
    let right = array.length -1;
    let mid = Math.floor((left + right) / 2);
    
    while (left <= right) {
        if(array[mid] === findValue) {
            return mid
        }
        
        if(array[mid] < findValue) {
            left = mid + 1;
        }else {
            right = mid - 1; 
        }
        
        mid = Math.floor((left + right) / 2);
    }
    
    return -1;
}