[JS 알고리즘] - 이진 검색 (Binary Search)

아래 강의를 듣고 내용을 정리한 포스트 입니다.

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

이진 검색은 선형 검색에 비해 훨씬 빠르게 검색을 완료할수 있습니다.
하나의 항목을 확인 할때마다 남은 항목의 절반을 없앨수 있습니다.
하지만 정렬된 리스트를 대상으로만 작동하므로 데이터가 정렬되어 있어야 합니다.

아래와 같이 정렬된 데이터가 있다고 가정해보겠습니다.

const US_States = [
    "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", "Florida", "Georgia",
    "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", "Louisiana", "Maine", "Maryland",
    "Massachusetts", "Michigan", "Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey",
    "New Mexico", "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", "Rhode Island", "South Carolina",
    "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
];

지난 선형 검색에서 했던것처럼 사용자가 Oregon 를 입력했다고 가정해보고, 이 배열안에 해당 주 가 있는지 찾아보도록 하겠습니다.

먼저 위 예제는, 이진 검색으로 검색 효율을 늘린다는 관점에서는 리스트가 너무 적습니다. 소요시간에도 큰 차이가 없을 것 입니다.
이진 검색을 사용해서 유의미한 검색 시간을 절약하지 않는다면 굳이 이진 검색을 사용할 메리트가 없습니다.
여기에서 사용한 예제로만 봐주시면 좋을것 같습니다.

알고리즘 접근법

먼저 이 배열은 알파벳순으로 분류가 되어 있기 때문에, 이 배열의 중간점(halfway point)을 선택합니다.
중간점이 어디에 있는지 정확하게 하나씩 셀 필요는 없습니다.
대략적으로 추측을 해서, 29번째 리스트를 선택합니다.
분류된 중간 항목이 중간점이 되어야합니다.
여기서 29번째 아이템은 "Missouri" 입니다.

이제 Oregon 이 Missouri 보다 앞에 있는지 뒤에 있는지를 알아야 합니다.
지금 경우엔 알파벳 순서 기준으로 정렬이 되있으므로, Oregon 은 Missouri 다음입니다.
따라서, Missouri 앞의 리스트는 신경쓸 필요가 없습니다.

다시 이 29번째 뒤에서부터 마지막 리스트의 중간 지점쯤 되는 44번째를 찾습니다.
이 44번째 지점은 "Pennsylvania" 입니다.
여기서 Oregon 은 Pennsylvania 보다 앞에 있습니다.
이제 Missouri 부터 Pennsylvania ( 29 ~ 44 ) 까지만 신경쓰면 됩니다.

이진 검색은 이런식으로 계속 반복하며 대상을 발견할때까지 찾습니다.

기본적인 아이디어는 분할 정복 (Divide and Conquer) 입니다.
배열을 중간지점을 하나 정하여 두 부분으로 나누고, 찾아야할 값이 중간점 기준으로 좌측 절반과 우측 절반중 어디에 있을지 확인합니다.

 

이진 검색 의사코드

- binarySearch 라는 함수를 작성. 정렬된 배열을 인자로 받는다.
- 2개의 인덱스(포인터)를 만든다. 하나는 계산을 시작하는 좌측 포인터, 배열의 마지막인 우측 포인터 이다.
- 같은 연산을 반복한다.
   1. 항목을 찾았는가? 항목을 찾지 못했으면 이진 검색을 계속한다.
   2. 좌측 포인터가 우측 포인터보다 앞에 있는 동안에만 연산이 이루어진다.
   3. 중간점은 좌측 포인터와 우측 포인터의 인덱스값 평균을 중간점으로 사용할수 있다.
   4. 항목을 찾았다면, 해당 인덱스를 반환한다.
   5. 값이 중간점보다 작다면, 중간점을 우측 포인터로 사용한다.
   6. 값이 중간점보다 크다면, 중간점을 좌측 포인터로 사용한다.
- 연산을 모두 했는데도 찾지 못하면, -1 을 반환한다.

저는 이 알고리즘을 while 문으로 구현해봤습니다.

function binarySearch(list: number[] | string[], target: number | string) {

  let leftPointer = 0;
  let rightPointer = list.length - 1;
  let middlePointer = Math.floor((rightPointer + leftPointer) / 2);

  while (
    leftPointer <= rightPointer &&
    leftPointer !== middlePointer &&
    rightPointer !== middlePointer
  ) {
    if (list[middlePointer] === target) {
      return middlePointer;
    } else if (list[leftPointer] === target) {
      return leftPointer;
    } else if (list[rightPointer] === target) {
      return rightPointer;
    }

    if (list[middlePointer] > target) {
      rightPointer = middlePointer;
    } else if (list[middlePointer] < target) {
      leftPointer = middlePointer;
    }

    middlePointer = Math.floor((rightPointer + leftPointer) / 2);
  }

  return -1;
}

 

조금더 로직을 다듬어 보자면, while loop 에서 좌측과 우측 포인터에 middlePointer 값으로 할당 필요가 없습니다.
추가로 while 문 안에서 바로 return 을 해버려서 함수의 동작 추측이 어렵습니다.
아래는 리팩터링 한 코드 입니다.

function binarySearch(list: number[] | string[], target: number | string) {
  let leftPointer = 0;
  let rightPointer = list.length - 1;
  let middlePointer = Math.floor((rightPointer + leftPointer) / 2);

  while (
    list[leftPointer] !== target &&
    list[middlePointer] !== target &&
    list[rightPointer] !== target &&
    leftPointer <= rightPointer &&
    middlePointer !== leftPointer &&
    middlePointer !== rightPointer
  ) {
    if (list[middlePointer] > target) {
      rightPointer = middlePointer - 1;
    } else if (list[middlePointer] < target) {
      leftPointer = middlePointer + 1;
    }

    middlePointer = Math.floor((rightPointer + leftPointer) / 2);
  }

  if (list[middlePointer] === target) {
    return middlePointer;
  } else if (list[leftPointer] === target) {
    return leftPointer;
  } else if (list[rightPointer] === target) {
    return rightPointer;
  }

  return -1;
}

binarySearch([1, 2, 3, 4, 5], 2) // 1
binarySearch([1, 2, 3, 4, 5], 6) // -1
binarySearch(
    [
      5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98,
      99,
    ],
    95
  ) // 16

 

코드 동작 해석

// target -> 2

[1, 2, 3, 4, 5]
 L     M     R

while 문에 들어가기 전, 포인터들은 위와같이 위치 합니다.
찾을 값이 2 가 들어온 경우, 값이 3 보다 작기 때문에 우측 포인터 R 이 왼쪽으로 움직여야 합니다.
이때 이미 3번째 인덱스를 검사했으므로, R 은 2번째 인덱스로 이동하면 됩니다.
그다음 M 은 1, 2 의 중간 값으로 2번째 인덱스가 됩니다.
다음 루프에 진입하기전, while 문의 조건세가지에 부합하지 않으므로 루프는 종료됩니다.

// target -> 2

[1, 2, 3, 4, 5]
 L  MR
 
// while문 조건들중 세가지
list[middlePointer] !== target
list[rightPointer] !== target
middlePointer !== rightPointer

target 값과 M번째 값이 같거나, target 값과 R번째 값이 같거나, M 포인터가 양쪽 포인터와 겹쳤을때 입니다.
target 은 M번째 값이랑 같으므로, 2번째 인덱스를 리턴합니다.

  if (list[middlePointer] === target) {
    return middlePointer; // 1
  } else if (list[leftPointer] === target) {
    return leftPointer;
  } else if (list[rightPointer] === target) {
    return rightPointer;
  }

 

값이 긴 경우도 보겠습니다.

// target -> 95

[5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99]
 L                                  M                                       R
 0                                  9                                       19
 
// 95는 40보다 크므로 L포인터 이동
[5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99]
                                        L               M                   R
                                        10              14                  19
                                        
// 95는 84보다 크므로 L포인터 이동
[5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99]
                                                            L       M       R
                                                            15      17      19
                                                            
// 95는 96보다 작으므로 R포인터 이동
[5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99]
                                                            L   M   R       
                                                            15  16  17
                                                            
// while문 조건들중 한가지
list[middlePointer] !== target // 95

// 어떤 경우의 값인지 확인
  if (list[middlePointer] === target) {
    return middlePointer; // 16
  } else if (list[leftPointer] === target) {
    return leftPointer;
  } else if (list[rightPointer] === target) {
    return rightPointer;
  }
  
return -1;

다른 입력으로, 값이 없는 경우도 코드 동작과 함께 살펴보겠습니다.

// target -> 6

[1, 2, 3, 4, 5]
 L     M     R
 
// 6은 3보다 크므로, L 포인터 이동
[1, 2, 3, 4, 5]
          LM R
 
// while문 조건들중 한가지
middlePointer !== leftPointer

// 어떤 경우의 값인지 확인
  if (list[middlePointer] === target) { // 해당없음
    return middlePointer;
  } else if (list[leftPointer] === target) { // 해당없음
    return leftPointer;
  } else if (list[rightPointer] === target) { // 해당없음
    return rightPointer;
  }
  
return -1; // 못찾음 반환

 

2번째 입력과 같이, 입력값이 클수록 이진검색은 선형검색에 비해 큰 효율을 가질수 있습니다. 3번의 루프를 통해 값을 찾아낼수 있었습니다.

 

이진 검색의 시간 복잡도

일반적으로 O(log n) 입니다.

따라서, 평균적으로 O(1) 에 거의 가깝습니다. 입력의 수가 많더라도, O(log n) 시간 안에 찾기 때문에 효율적입니다.

여기서 시간 복잡도를 계산하는 것은 다음에 다뤄 보도록 하겠습니다.

언제 사용하는가?

-> 정렬이 되어 있는 데이터 일때
-> 입력 리스트가 많을때