Programme de recherche binaire écrit en langage C, utilisant pthread pour le traitement multi-thread

Nous savons que la méthode de recherche binaire est l'algorithme de tri le plus adapté et le plus efficace. Cet algorithme fonctionne sur des séquences triées. L'algorithme est simple, il trouve simplement l'élément du milieu, puis divise la liste en deux parties et se déplace vers la sous-liste de gauche ou la sous-liste de droite.

Nous connaissons son algorithme. Nous allons maintenant voir comment utiliser la technique de recherche binaire dans un environnement multi-thread. Le nombre de threads dépend du nombre de cœurs présents dans le système. Jetons un coup d'œil au code pour avoir une idée.

Exemple

#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;
}

Sortie

31 found in array

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!