Binary search is a popular method of searching in a sorted array or list. It simply divides the list into two halves and discards the half which has zero probability of having the key. On dividing, we check the midpoint for the key and use the lower half if the key is less than the midpoint and the upper half if the key is greater than the midpoint. Binary search has a time complexity of O(log(n)). Binary search can also be implemented using multi-threading where we utilize the cores of the processor by providing each thread a portion of the list to search for the key. The number of threads depends upon the number of cores your processor has and it’s better to create one thread for each core. Examples:
Input : list = 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220
key = 7
Output : 7 found in list
Input : list = 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220
key = 111
Output : 111 not found in list
Note – It is advised to execute the program in Linux based system. Compile in Linux using the following code:
g++ -pthread program_name.cpp
CPP
// 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 searchedint a[] = { 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220 };// key that needs to be searchedint 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 Codeint 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) cout << key << " found in array" << endl; // key not found in array else cout << key << " not found in array" << endl; return 0;} |
Python3
# Python3 Program to find sum of array# using multi-threadingfrom threading import Thread# Size of arrayMAX = 16# Maximum number of threadsMAX_THREAD = 4# Initial arrayarr = [1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220]# Key that needs to be searchedkey = 110found = Falsepart = 0# Function to perform Binary Searchdef binary_search(): global part, found thread_part = part part += 1 # Each thread checks 1/4 of the array for the key low = int(thread_part*(MAX/4)) high = int((thread_part+1)*(MAX/4)) # search for the key until low < high # or key is found in any portion of array while (low < high and not found): # normal iterative binary search algorithm mid = int(low + (high-low)/2) if arr[mid] == key: found = True break elif arr[mid] > key: high = mid - 1 else: low = mid + 1# Driver Codeif __name__ == "__main__": # Creating list of size MAX_THREAD thread = list(range(MAX_THREAD)) # Creating MAX_THEAD number of threads for i in range(MAX_THREAD): thread[i] = Thread(target=binary_search) thread[i].start() # Waiting for all threads to finish for i in range(MAX_THREAD): thread[i].join() # Key found in array if found: print("%d found in array" % key) else: print("%d not found in array" % key) |
C#
using System;using System.Threading;public class Program { // Size of array const int MAX = 16; // Maximum number of threads const int MAX_THREAD = 4; // Initial array static int[] arr = { 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220 }; // Key that needs to be searched static int key = 110; static bool found = false; static int part = 0; // Function to perform Binary Search static void BinarySearch() { int thread_part = Interlocked.Increment(ref part) - 1; // Each thread checks 1/4 of the array for the key 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 int mid = low + (high - low) / 2; if (arr[mid] == key) { found = true; break; } else if (arr[mid] > key) { high = mid - 1; } else { low = mid + 1; } } } // Driver Code static void Main() { // Creating array of size MAX_THREAD Thread[] thread = new Thread[MAX_THREAD]; // Creating MAX_THREAD number of threads for (int i = 0; i < MAX_THREAD; i++) { thread[i] = new Thread(new ThreadStart(BinarySearch)); thread[i].Start(); } // Waiting for all threads to finish for (int i = 0; i < MAX_THREAD; i++) { thread[i].Join(); } // Key found in array if (found) { Console.WriteLine("{0} found in array", key); } else { Console.WriteLine("{0} not found in array", key); } }}// This code is contributed by shiv1o43g |
Java
import java.util.concurrent.atomic.AtomicInteger;public class Program { // Size of array static final int MAX = 16; // Maximum number of threads static final int MAX_THREAD = 4; // Initial array static int[] arr = { 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220 }; // Key that needs to be searched static int key = 110; static boolean found = false; static AtomicInteger part = new AtomicInteger(0); // Function to perform Binary Search static void binarySearch() { int thread_part = part.getAndIncrement(); // Each thread checks 1/4 of the array for the key int low = thread_part * (MAX / 4); int high = (thread_part + 1) * (MAX / 4); while (low < high && !found) { // Normal iterative binary search algorithm int mid = low + (high - low) / 2; if (arr[mid] == key) { found = true; break; } else if (arr[mid] > key) { high = mid - 1; } else { low = mid + 1; } } } // Driver Code public static void main(String[] args) { Thread[] thread = new Thread[MAX_THREAD]; for (int i = 0; i < MAX_THREAD; i++) { thread[i] = new Thread(new Runnable() { public void run() { binarySearch(); } }); thread[i].start(); } for (int i = 0; i < MAX_THREAD; i++) { try { thread[i].join(); } catch (InterruptedException e) { e.printStackTrace(); } } if (found) { System.out.printf("%d found in array\n", key); } else { System.out.printf("%d not found in array\n",key); } }}// This code is contributed by shivhack999 |
Output
110 found in array
Time complexity: O(log(n))
Space complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
