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

유데미 쉽게 배우는 JavaScript 알고리즘 입문 강의의 내용을 정리한 글입니다.

검색 알고리즘이란?

검색 알고리즘이란 말 그대로 주어진 데이터 내에서 특정 데이터를 검색하여 찾아내는 알고리즘이다. 순차 검색 알고리즘, 이진 검색 알고리즘, 해쉬 탐색 알고리즘 등 종류가 많다. 검색 알고리즘이라고도 하고 탐색 알고리즘이라는 이름을 쓰기도 하는데, 강의에서 검색이라는 용어를 사용하셨기 때문에 나도 검색 알고리즘이라고 표기하겠다! 

이진 검색 알고리즘이란?

• Divide and Conquer : "분할과 정복" 방식이라고 할 수 있는데, 정리하면 두 부분씩 쪼개어 범위를 좁혀가며 검색한다는 의미이다. 
• 정렬되어 있는 데이터를 먼저 절반으로 나눈뒤, 절반에 위치한 데이터(mid 데이터)와 타겟 데이터를 비교한다. mid 기준 타겟이 더 클 경우 범위는 mid를 기준으로 큰 쪽으로 좁혀야 하고, 따라서 그보다 작은 나머지 절반은 무시한다. 반대로 mid 기준 타겟이 더 작을 경우는, mid를 기준으로 작은 쪽으로 범위를 좁히고 나머지 절반은 무시한다.
• 이렇게 절반씩 쪼개어 비교하기 때문에, 모든 데이터를 돌며 하나씩 비교해야하는 순차 검색에 비해서 훨씬 빠르다고 할 수 있다. 
• 데이터들은 이진 검색 이전에 먼저 정렬이 되어 있어야 한다. 그래야 mid 값을 기준으로 두 부분을 비교했을 때 올바른 범위를 설정할 수 있다. 

출처 : https://velog.io/@crystalhwang16/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-binary-search

아래 코드를 보면서 더 자세하게 살펴보자!

• 오름차순으로 정렬된 1차원 배열 data가 있다. 
• 찾을 데이터 search 는 9이고, 찾은 상태와 인덱스를 추적하기 위해서 각각 flag와 index 변수를 미리 만들어주자.
• 배열의 가운데 값을 찾는 방법은, 초기에 가장 작은 인덱스값 0과 가장 큰 인덱스값 length - 1 두 값을 더해 반으로 나누는 것이다.
• while문 내에서 범위가 좁혀져서 low와 high가 만나는 순간까지 각 검색을 반복하면서 low 혹은 high를 mid 값을 기준으로 계속 변화시켜준다.
• mid 값은 좁혀진 범위의 mid 값으로 계속 갱신되므로 반복문 내에서 매번 새롭게 선언해주자. 
• 만약 이 mid 인덱스에 위치한 값이 찾고 있는 값과 같아진다면, flag와 index를 각각에 맞게 변경된 뒤 break로 반복문을 탈출한다. 그리고 결과를 출력한다.
• 만약 현재 mid 값이 찾고 있는 데이터에 비해 크다면, 찾고 있는 데이터는 그보다 작은 영역에 위치할 것이기 때문에 high 값을 mid의 바로 직전으로 옮겨준다.
• 반대로 mid 값이 찾고 있는 데이터에 비해서 작다면, 그보다 더 큰 영역에서 검색해야하기 때문에 low 값을 mid의 바로 다음으로 옮겨준다. 
• 모든 반복을 거쳤는데도 값을 찾지 못했다면, 초기에 설정한 index = -1 이 찍힌 결과값을 보게 될 것이고, 검색에 성공하였다면 해당 결과값이 반영된 결과가 나올 것이다.

(() => {
  const data = [1, 3, 5, 7, 9, 11, 13];
  const N = data.length;
  let search = 9;
  let flag = false;
  let index = -1;

  let low = 0;
  let high = N - 1;
  while (low <= high) {
    let mid = parseInt((low + high) / 2);

    if (data[mid] === search) {
      flag = true;
      index = mid;
      break;
    } else if (data[mid] > search) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  // output
  if (flag) {
    console.log(`Search Data ${search} was found in index ${index}`);
  } else {
    console.log('찾지 못했습니다 ㅠㅠ.');
  }
})();

// Search Data 9 was found in index 4

+ 시간 복잡도

O(logn) 절반씩 줄여나가기 때문에 그렇다.