C言語でpthreadを使ったマルチスレッド二分探索の実装方法

二分探索（バイナリサーチ）は、ソート済みのデータ列に対して最も適しており、効率的な探索アルゴリズムの一つとして知られています。仕組みは非常にシンプルで、まず配列の中央にある要素を調べ、そこからリストを2つに分割します。そして、目的のキーとの大小関係に応じて、左側の部分リストか右側の部分リストのどちらか一方だけを探索対象として絞り込んでいくのです。

基本的なアルゴリズムはすでに理解している前提で、今回は二分探索をマルチスレッド環境で実装する方法を見ていきましょう。生成するスレッド数は、システムに搭載されているCPUコアの数に依存します。以下のコードで具体的なイメージをつかんでください。

サンプルコード

#include <iostream>
#define MAX 16
#define MAX_THREAD 4
using namespace std;
// 配列・キー・その他の変数は、複数スレッドからアクセスできるようグローバルに配置
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); // 担当範囲から開始位置と終了位置を設定
   int end = (thread_part + 1) * (MAX / 4);
   // low < high の間、またはキーが見つかるまで探索を続ける
   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

コードのポイント

このプログラムでは、16個の要素を持つソート済み配列を4つのスレッドに均等に分割し、各スレッドが担当範囲内で独立して二分探索を行います。グローバル変数 found を共有することで、あるスレッドがキーを発見した時点で他のスレッドも探索を打ち切れるように設計されています。

なお、pthreadライブラリを使用するため、コンパイル時には -lpthread オプションを付ける必要があります（例：g++ sample.cpp -lpthread）。また、実際の環境では part や found への同時アクセスを考慮し、必要に応じてミューテックスやアトミック操作による同期を検討するとより安全です。