La búsqueda binaria es un método popular de búsqueda en una array o lista ordenada. Simplemente divide la lista en dos mitades y descarta la mitad que tiene cero probabilidad de tener la clave. Al dividir, verificamos el punto medio para la clave y usamos la mitad inferior si la clave es menor que el punto medio y la mitad superior si la clave es mayor que el punto medio. La búsqueda binaria tiene una complejidad temporal de O(log(n)).
La búsqueda binaria también se puede implementar utilizando subprocesos múltiples donde utilizamos los núcleos del procesador proporcionando a cada subproceso una parte de la lista para buscar la clave.
La cantidad de subprocesos depende de la cantidad de núcleos que tenga su procesador y es mejor crear un subproceso para cada núcleo.
Ejemplos:
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
Nota: se recomienda ejecutar el programa en un sistema basado en Linux.
Compile en Linux usando el siguiente código:
g++ -pthread program_name.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 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)
cout << key << " found in array" << endl;
// key not found in array
else
cout << key << " not found in array" << endl;
return 0;
}
Producción:
110 found in array
Publicación traducida automáticamente
Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA