การค้นหาแบบทวิภาคโดยใช้ pthread ในโปรแกรม C

เรารู้ว่าการค้นหาแบบทวิภาคเป็นอัลกอริทึมที่เหมาะสมและมีประสิทธิภาพ ทำงานบนลำดับที่จัดเรียงแล้ว อัลกอริทึมค่อนข้างง่าย หาองค์ประกอบจากกลาง แล้วแบ่งรายการเป็นสองส่วน และเคลื่อนไปยังสับรายการซ้ายหรือขวา

ตอนนี้เราจะดูวิธีใช้การค้นหาแบบทวิภาคในสภาพแวดล้อมมัลติเธรด จำนวนเธรดขึ้นอยู่กับจำนวนโคร์ในระบบ ให้ดูโค้ดเพื่อเข้าใจ

ตัวอย่าง

#include 
#define MAX 16
#define MAX_THREAD 4
using namespace std;
// วาง arr, key และตัวแปรอื่นๆ เป็น global เพื่อเข้าถึงจากเธรดต่างๆ
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); // กำหนด start และ end โดยใช้ส่วนของเธรด
    int end = (thread_part + 1) * (MAX / 4);
    // ค้นหา key จนกว่า low < high
    // หรือพบ 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