Chúng ta biết rằng cách tiếp cận tìm kiếm nhị phân là một trong những thuật toán sắp xếp phù hợp và hiệu quả nhất. Điều này hoạt động trên trình tự được sắp xếp. Thuật toán rất đơn giản, nó chỉ cần tìm phần tử từ giữa, sau đó chia danh sách thành hai phần và di chuyển sang danh sách con bên trái hoặc danh sách con bên phải.
Chúng tôi biết thuật toán của nó. Bây giờ chúng ta sẽ xem cách sử dụng kỹ thuật tìm kiếm nhị phân trong môi trường đa luồng. Số luồng phụ thuộc vào số lõi có trong hệ thống. Hãy cho chúng tôi xem mã để biết ý tưởng.
Ví dụ
#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;
} Đầu ra
31 found in array