윤성우의 열혈 자료구조를 읽고 복습한 내용입니다.

이진 탐색(Binary) 알고리즘의 소개

이진 탐색 알고리즘은 앞서 설명한 순차 탐색 알고리즘보다 훨씬 좋은 성능을 보인다. 하지만 배열을 대상으로 이진 탐색 알고리즘을 적용하기 위해서는 다음의 조건을 만족해야만 한다.

배열에 저장된 데이터는 정렬되어 있어야 한다.

즉, 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. 그렇기 때문에 이진 탐색 알고리즘보다 성능이 덜한 순차 탐색 알고리즘도 우리에게는 유용한 알고리즘이다.

이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다. 그렇기 때문에 앞서 소개한 순차 탐색 알고리즘에 비해 좋은 성능을 보인다.

탐색의 범위가 줄어드는 형태는 위의 그림과 같다. 탐색의 시작위치에 해당하는 인덱스 값을 first, 탐색의 마지막 위치에 해당하는 인덱스 값을 last라고 하면, 이 그림에서 보이는 바와 같이 이진 탐색 알고리즘이 진행됨에 따라서 first와 last는 가까워진다. 이진 탐색 알고리즘은 first가 last보다 큰 경우 탐색이 종료된다. 그리고 이렇게 종료가 되었다는 것은 탐색에 실패했음을 의미한다.

const BSearch = (arr, target) => {
  let first = 0; // 탐색 대상의 시작 인덱스 값
  let last = arr.length - 1; // 탐색 대상의 마지막 인덱스 값
  let mid;

  while(first <= last){
    mid = Math.floor((first+last) / 2); // 탐색 대상의 중간 인덱스 값
    if(target === arr[mid])
      return mid; // 탐색 완료
    else // 중간 값이 타겟이 아니라면 탐색 대상을 반으로 줄인다.
    {
      if(target < arr[mid]) last = mid - 1;
      else first = mid + 1;
    }
    console.log(first, last, mid);
  }
  return -1; // 찾지 못했을 때 반환되는 값
}

const arr = [1, 3, 5, 7, 9];
let idx;

idx = BSearch(arr, 7);
if(idx === -1) console.log("탐색 실패");
else console.log(`타겟 저장 인덱스: ${idx}`);
// 타겟 저장 인덱스: 3 출력

idx = BSearch(arr, 4);
if(idx === -1) console.log("탐색 실패");
else console.log(`타겟 저장 인덱스: ${idx}`);
// 탐색 실패 출력

BSearch 함수가 이진 탐색 알고리즘의 구현에 해당한다.

이진 탐색 알고리즘의 시간 복잡도 계산하기: 최악의 경우(worst case)를 기준으로

이진 탐색 알고리즘도 순차 탐색 알고리즘과 마찬가지로 === 연산을 연산횟수를 대표하는 연산으로 볼 수 있다. 데이터의 수가 n개일 때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 되는지 생각해보자.

• 처음에 데이터의 수가 n개일 때의 탐색과정에서 1회 비교연산 진행
• 데이터의 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행
• 데이터의 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행
  ...
• 데이터의 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회 비교연산 진행

이는 데이터의 수 n을 대상으로 다음과 같이 일반화할 수 있다.

• n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행
• 데이터가 1개 남았을 때, 마지막으로 비교연산 1회 진행

최악의 경우에 대한 시간 복잡도 함수 T(n) = k + 1 이다.

n이 1이 되기까지 2로 나눈 횟수가 k이니, n과 k에 관한 식은 다음과 같다.

이 식을 정리하면 k에 대해 정리하면 다음과 같다.

따라서 이진 탐색 알고리즘의 최악의 경우에 대한 시간 복잡도 함수 T(n)은 다음과 같다.

최악의 경우에 대한 시간 복잡도 함수 T(n) = k + 1 이지만, +1은 중요하지 않고 데이터의 수 n이 증가함에 따라서 비교연산 횟수가 로그적으로 증가한다는 사실이 중요하다. 앞서 성능분석에 대해 다뤘을 때, "식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다" 고 얘기했었다. 즉, n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않다.