이진탐색(Binary Search)

이진탐색은 정렬된 배열 리스트에서 원하는 요소를 찾을 때 사용하는 탐색 알고리즘이다. 배열에서 탐색범위를 절반씩 좁혀가면서 특정한 값을 찾는 방법인데, 속도가 빠르고 효율적이여서 알아두면 좋은 알고리즘이다.

 

❗️ indexOf 메서드를 사용하면 원하는 값을 찾을 수 있는데, 이진탐색이 필요할까?

indexOf 메서드의 시간 복잡도는 O(n)이고, 이진탐색의 시간 복잡도는 O(log n)이다. 그렇기 때문에 정렬된 배열이 주어진다면 indexOf 메서드보다 이진탐색을 사용하는게 더 빠르고 효율적이다.

 

위에서 설명했듯이 이진탐색은 탐색범위를 절반씩 좁혀가며 값을 찾는 방법이다. 이진탐색의 원리에 대해 생각해보자.

1. 배열에서 중간 값을 찾는다.
2. 찾는 값이 중간 값보다 크면 탐색 범위를 중간부터 끝까지, 작다면 탐색 범위를 처음부터 중간까지로 변경한다.
3. 중간 값이 원하는 값과 같을 때까지 위 과정을 반복한다.

 

예시를 통해서 이진탐색이 진행되는 과정을 알아보자.

let target = 23;
let arr = [1, 2, 3, 9, 10, 15, 23, 30, 35, 40];

 

1. 배열의 중간 값은 10이다. 23은 10보다 큰 숫자이기 때문에 찾는 범위를 [15, 23, 30, 25, 40]으로 줄인다.
2. [15, 23, 30, 25, 40] 에서 중간 값은 30이다. 23은 30보다 작은 숫자이기 때문에 찾는 범위를 [15, 23]으로 줄인다.
3. [15, 23] 에서 중간 값은 15이다. 23은 15보다 크기 때문에 찾는 범위를 [23]으로 줄인다.
4. [23] 에서 중간 값은 23이다. 여기서 23을 찾을 수 있다.

 

위 과정을 코드로 작성하면 아래와 같다.

function binarySearch(arr, target) {
    let low = 0;
    let hight = arr.length - 1;

    while (low <= hight) {
      let middle = Math.floor((low + hight) / 2);

      if (target < arr[middle]){
        hight = middle - 1;
      } else if (target > arr[middle]){
        low = middle + 1;
      } else {
        return middle;
      }
    }
    return -1;
  }

console.log(binarySearch([1, 2, 3, 9, 10, 15, 23, 30, 35, 40], 10)); // 4
console.log(binarySearch([1, 2, 5, 6, 7, 8, 9, 10, 11, 12], 10)); // 7
console.log(binarySearch([10, 20, 30, 40, 50, 60, 70], 80)); // -1

 

binarySearch 함수는 정렬된 배열이 주어졌을 때, 찾고자 하는 값을 찾는다면 해당 값의 인덱스를 반환하고, 없다면 -1을 반환하는 함수이다.