Tìm kiếm nhị phân dùng pthread trong C

Triển khai tìm kiếm nhị phân song song bằng pthread. Mảng đã sắp xếp, chia thành 4 phần, mỗi luồng tìm kiếm trên 1 phần.

Ví dụ

#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) {
    int thread_part = part++;
    int start = thread_part * (MAX/4);
    int end = (thread_part+1) * (MAX/4);
    int mid;
    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;
    }
}

int main() {
    pthread_t threads[MAX_THREAD];
    for (int i = 0; i < MAX_THREAD; i++)
        pthread_create(&threads[i], NULL, binary_search, 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;
}

Kết quả

31 found in array