C 프로그램에서 pthread를 사용한 이진 검색?

바이너리 검색 방식이 가장 적합하고 효과적인 정렬 알고리즘 중 하나라는 것을 알고 있습니다. 이것은 정렬된 순서에서 작동합니다. 알고리즘은 간단합니다. 중간에서 요소를 찾은 다음 목록을 두 부분으로 나누고 왼쪽 하위 목록이나 오른쪽 하위 목록으로 이동합니다.

우리는 그 알고리즘을 알고 있습니다. 이제 멀티스레딩 환경에서 바이너리 검색 기술을 사용하는 방법을 알아보겠습니다. 스레드 수는 시스템에 있는 코어 수에 따라 다릅니다. 아이디어를 얻기 위해 코드를 살펴보겠습니다.

예시

#include <iostream>
#define MAX 16
#define MAX_THREAD 4
using namespace std;
//place arr, key and other variables as global to access from different thread
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) {
   // There are four threads, each will take 1/4th part of the list
   int thread_part = part++;
   int mid;
   int start = thread_part * (MAX / 4); //set start and end using the thread part
   int end = (thread_part + 1) * (MAX / 4);
   // search for the key until low < high
   // or key is found in any portion of array
   while (start < end && !found) { //if some other thread has got the element, it will stop
      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); //wait, to join with the main thread
   if (found)
      cout << key << " found in array" << endl;
   else
      cout << key << " not found in array" << endl;
}

출력

31 found in array