[알고리즘] 이진 검색 [Binary Search]

[알고리즘] 이진 검색 [Binary Search]

이진 검색(Binary Search)은 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 알고리즘입니다.

이 알고리즘은 다음과 같은 단계를 따릅니다

 

 

 

주의

이진 검색은 분류된 배열을 대상으로만 작동함으로 데이터가 분류되어있어야 한다.

낮은 수에서 큰 수로, 알파벳 순으로 등등 순서가 있어야 한다.

 

 

 

 

기본 개념

분할 정복 (divide and conquer)

배열을 중간을 기준으로 나누고, 그 중간의 죄측 절반 / 우측 절반에 있을지 확인

 

 

 

 

 

이진 검색 방법

중간 값 확인

배열의 중간 값을 확인합니다.

 

 

비교

찾고자 하는 값과 중간 값을 비교합니다.

• 찾고자 하는 값이 중간 값보다 작으면, 배열의 왼쪽 절반을 탐색합니다.
• 찾고자 하는 값이 중간 값보다 크면, 배열의 오른쪽 절반을 탐색합니다.

 

반복

배열의 크기가 0이 될 때까지 이 과정을 반복합니다.

 

 

이진 검색은 배열이 정렬되어 있을 때만 사용할 수 있으며, 시간 복잡도는 O(log n)입니다.

 

 

 

 

예시

정렬된 배열과 값을 받아들이고 값이 존재하는 경우 그 인덱스를 반환하는 binarySearch라는 함수를 작성합니다.

값이 존재하지 않으면 -1을 반환합니다.

이 알고리즘은 linearSearch 보다 더 효율적일 것입니다.

  

    
    
    
    
  
function binarySearch(arr, num){
    let start = 0;
    let end = arr.length - 1;
    let middle  = Math.floor((start + end) / 2)
    while(arr[middle] !== num && start <= end) {
        if (arr[middle] > num) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === num ? middle : -1;
}

binarySearch([2, 5, 6, 9, 13, 15, 28, 30], 13);

 

 

 

 

 

이진 검색의 시간 복잡도? (Big O)

 

 

 

 

 

 

참조!

https://www.udemy.com/course/best-javascript-data-structures/