Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - Search - Binary Search using pthread ======

Binary search is a popular method of searching in a sorted array or list.

  * It simply divides the list into two halves and discard the half which has zero probability of having the key.
  * On dividing we check the mid point for the key and uses the lower half if key is less than mid point and upper half if key is greater than mid point.
  * Binary search has time complexity of O(log(n)).

Binary search can also be implemented using __multi-threading__ where we utilizes the cores of processor by providing each thread a portion of list to search for the key.

Number of threads depends upon the number of cores your processor has and its better to create one thread for each core.

----

===== Example =====

<code cpp>
// Program to perform binary search using pthreads.
#include <iostream> 
using namespace std; 
  
// Size of array.
#define MAX 16 
  
// Maximum number of threads.
#define MAX_THREAD 4 
  
// Array to be searched.
int a[] = { 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220 }; 
  
// Key that needs to be searched.
int key = 110; 

bool found = false; 
int part = 0; 
  
void* binary_search(void* arg) 
{ 
  // Each thread checks 1/4 of the array for the key.
  int thread_part = part++; 
  int mid; 
  
  int low = thread_part * (MAX / 4); 
  int high = (thread_part + 1) * (MAX / 4); 
  
  // Search for the key until low < high or key is found in any portion of array.
  while (low < high && !found)
  { 
    // Normal iterative binary search algorithm.
    mid = (high - low) / 2 + low; 
  
    if (a[mid] == key)
    { 
      found = true; 
      break; 
    } 
    else
    if (a[mid] > key) 
      high = mid - 1; 
    else
      low = mid + 1; 
  } 
} 
  
  
// Driver Code.
int 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); 
  
  // Key found in array.
  if (found) 
    std::cout << key << " found in array" << std::endl; 
  
  // Key not found in array.
  else
    std::cout << key << " not found in array" << std::endl; 
  
  return 0; 
} 
</code>

returns:

<code>
110 found in array
</code>

<WRAP info>
**NOTE:** Compile with:

<code bash>
g++ -pthread program_name.cpp
</code>

</WRAP>

----