C++로 구현하는 균일 이진 검색(Uniform Binary Search) 프로그램

균일 이진 검색(Uniform Binary Search)은 룩업 테이블(lookup table)을 활용하여 이진 검색을 구현하는 기법입니다. 일반적인 이진 검색에서는 매 단계마다 중간 위치를 계산하기 위해 시프트와 덧셈 연산을 반복해야 하지만, 균일 이진 검색은 미리 계산해 둔 오프셋 테이블을 조회하기만 하면 되므로 실행 속도가 더 빠릅니다. 이 방식의 시간 복잡도는 O(log(n))으로 일반 이진 검색과 동일하지만, 상수 수준의 성능 개선 효과를 얻을 수 있습니다.

알고리즘

시작
    데이터를 정렬된 상태로 배열에 저장한다.
    룩업 배열의 최대 길이를 계산하고 새 배열 'del'을 선언한다.
    룩업 배열에 n/2, n/4, ... 순으로 값이 '0'이 될 때까지 저장한다.
    (여기서 n은 데이터 배열의 길이)
    UniBinarySearch() 함수를 호출한다.
    mid를 'del' 배열의 0번 인덱스 값으로 설정하고,
    key와 mid 인덱스 위치의 값을 비교한다.
    두 값이 같으면 해당 인덱스를 main 함수로 반환한다.
    'del' 배열의 현재 값이 0이면 요소가 존재하지 않으므로 -1을 반환한다.
    key가 더 작으면 'del' 배열의 다음 값을 빼고 포인터를 다음 칸으로 이동한다.
    key가 더 크면 'del' 배열의 다음 값을 더하고 포인터를 다음 칸으로 이동한다.
    함수가 반환한 인덱스를 출력하고, 추가 검색 여부를 사용자에게 묻는다.
끝

예제 코드

#include <iostream>
using namespace std;

// 룩업 테이블 생성: n/2, n/4, ... 순으로 오프셋 저장
void lookUpArray(int *a, int N) {
   int power = 1, i = 0;
   do {
      int half = power;
      power *= 2;
      a[i] = (N + half) / power;
      i++;
   } while (a[i - 1] != 0);
}

// 균일 이진 검색 함수
int UniBinarySearch(int *a, int *dal, int key) {
   int i = dal[0] - 1, d = 0;
flag:
   if (key == a[i])
      return i;              // 요소를 찾으면 인덱스 반환
   else if (dal[d] == 0)
      return -1;             // 탐색 범위가 끝나면 -1 반환
   else {
      if (key < a[i]) {
         i -= dal[++d];      // 왼쪽 부분으로 이동
         goto flag;
      }
      else {
         i += dal[++d];      // 오른쪽 부분으로 이동
         goto flag;
      }
   }
}

int main(void) {
   int n = 10, d = 0, pow = 1, index, key;
   char ch;
   int a[10] = {2, 6, 7, 10, 12, 14, 16, 18, 20, 26};

   // 룩업 배열의 최대 길이 계산
   while (pow <= n) {
      pow *= 2;
      d++;
   }
   int del[d];
   lookUpArray(del, n);

up:
   cout << "\nEnter the Element to be searched: ";
   cin >> key;
   index = UniBinarySearch(a, del, key);

   if (index == -1)
      cout << "\nItem not found";
   else
      cout << "\nItem " << key << " found at " << index + 1 << " position";

   cout << "\n\n\tDo you want to search more...enter choice(y/n)?";
   cin >> ch;
   if (ch == 'y' || ch == 'Y')
      goto up;

   return 0;
}

코드 설명

lookUpArray() 함수는 데이터 배열의 길이 N을 절반씩 나누어 가며 오프셋 값(n/2, n/4, ...)을 룩업 테이블에 저장합니다. 검색 시에는 이 테이블의 값을 순차적으로 참조하면서 현재 위치에서 더하거나 빼는 방식으로 탐색 범위를 좁혀 갑니다. 매번 중간 지점을 새로 계산하는 대신 미리 준비된 값을 조회만 하면 되기 때문에, 분기 예측과 연산 비용 측면에서 유리합니다.

단, 이 알고리즘이 올바르게 동작하려면 입력 배열이 반드시 오름차순으로 정렬되어 있어야 하며, 중복된 값이 없는 것이 좋습니다.

실행 결과

Enter the Element to be searched: 7
Item 7 found at 3 position

	Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 21
Item not found

	Do you want to search more...enter choice(y/n)?n

실행 결과를 보면 사용자가 검색한 값 7은 배열의 3번째 위치에서 발견되었고, 배열에 존재하지 않는 값 21을 검색했을 때는 "Item not found" 메시지가 출력됩니다. 프로그램은 y/Y를 입력하면 추가 검색을 계속 진행합니다.