이진 검색(Binary Search)은 정렬된 데이터 집합에서 원하는 값을 빠르게 찾아내는 가장 효율적인 탐색 알고리즘 중 하나로 널리 알려져 있습니다. 이 알고리즘은 반드시 정렬된 시퀀스에서만 동작하며, 그 원리는 매우 간단합니다. 먼저 리스트의 가운데 위치한 요소와 찾으려는 값을 비교한 뒤, 리스트를 절반으로 나누어 값이 존재할 가능성이 있는 왼쪽 또는 오른쪽 부분 리스트로 탐색 범위를 좁혀 나갑니다.
기본적인 이진 검색 알고리즘은 이미 많이 알려져 있는데요, 이번 글에서는 pthread 라이브러리를 활용해 멀티스레딩 환경에서 이진 검색을 구현하는 방법을 살펴보겠습니다. 생성할 스레드의 개수는 일반적으로 시스템에 장착된 CPU 코어 수에 맞추는 것이 효율적입니다. 그럼 예제 코드를 통해 구체적인 구현 방법을 확인해 보겠습니다.
예제 코드
#include <iostream>
#define MAX 16
#define MAX_THREAD 4
using namespace std;
// 여러 스레드에서 접근할 수 있도록 arr, key 등의 변수를 전역으로 선언
int arr[] = { 1, 6, 8, 11, 13, 14, 15, 19, 21, 23, 26, 28, 31, 65, 108, 220 };
int key = 31;
bool found = false;
int part = 0;
void* binary_search(void* arg) {
// 4개의 스레드가 각각 리스트의 1/4 영역을 담당
int thread_part = part++;
int mid;
int start = thread_part * (MAX / 4); // thread_part 값을 이용해 시작·끝 인덱스 설정
int end = (thread_part + 1) * (MAX / 4);
// start < end 조건이 유지되는 동안,
// 또는 어떤 스레드도 key를 찾지 못한 상태에서 탐색을 계속 진행
while (start < end && !found) { // 다른 스레드가 해당 요소를 찾았다면 탐색 중단
mid = (end - start) / 2 + start;
if (arr[mid] == key) {
found = true;
break;
}
else if (arr[mid] > key)
end = mid - 1;
else
start = mid + 1;
}
}
main() {
pthread_t threads[MAX_THREAD];
for (int i = 0; i < MAX_THREAD; i++)
pthread_create(&threads[i], NULL, binary_search, (void*)NULL);
for (int i = 0; i < MAX_THREAD; i++)
pthread_join(threads[i], NULL); // 모든 스레드가 종료될 때까지 대기 후 합류
if (found)
cout << key << " found in array" << endl;
else
cout << key << " not found in array" << endl;
}실행 결과
31 found in array
코드 동작 원리
1. 작업 분할
전체 배열(16개 요소)을 스레드 개수(4개)만큼 균등하게 나누어 각 스레드가 4개의 요소로 이루어진 구간을 담당하도록 설계했습니다. 전역 변수 part를 이용해 각 스레드에 고유한 구간 번호를 순차적으로 할당하고, 이 번호를 바탕으로 탐색 범위의 시작 인덱스와 끝 인덱스를 계산합니다.
2. 독립적 탐색
각 스레드는 자신에게 할당된 구간 안에서 별도의 이진 검색을 독립적으로 수행합니다. 이렇게 하면 하나의 스레드가 처음부터 끝까지 배열 전체를 탐색하는 것보다 탐색 속도를 크게 향상시킬 수 있습니다.
3. 조기 종료(Early Termination)
공유 변수 found가 핵심 역할을 합니다. 어느 한 스레드라도 key 값을 발견하면 found가 true로 설정되고, 나머지 스레드들은 while 루프 조건을 만족하지 못해 더 이상 불필요한 탐색을 하지 않고 즉시 종료됩니다.
4. 결과 취합
pthread_join() 함수를 호출해 모든 스레드의 작업이 완료될 때까지 메인 스레드가 대기한 뒤, found 값에 따라 key가 배열에 존재하는지 여부를 최종 출력합니다.
컴파일 방법
참고로 위 코드는 C++ 문법(iostream 사용)으로 작성되었습니다. Linux 환경에서 컴파일할 때는 pthread 라이브러리를 링크하기 위해 다음과 같이 -lpthread 옵션을 반드시 추가해야 합니다.
g++ program.cpp -lpthread -o program
이처럼 pthread를 활용하면 이진 검색을 멀티코어 환경에서 병렬로 처리할 수 있어, 대규모 정렬 데이터에서 원하는 값을 더욱 신속하게 찾을 수 있습니다.