Home > Backend Development > C++ > body text

Binary search program written in C language, using pthread for multi-thread processing

WBOY
Release: 2023-08-26 12:45:12
forward
1273 people have browsed it

Binary search program written in C language, using pthread for multi-thread processing

#We know that the binary search method is the most suitable and effective sorting algorithm. This algorithm works on sorted sequences. The algorithm is simple, it just finds the element from the middle, then splits the list into two parts and moves to the left sublist or the right sublist.

We know its algorithm. Now we will see how to use the binary search technique in a multi-threaded environment. The number of threads depends on the number of cores present in the system. Let's take a look at the code to get the idea.

Example

#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;
}
Copy after login

Output

31 found in array
Copy after login

The above is the detailed content of Binary search program written in C language, using pthread for multi-thread processing. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template