En este artículo, analizaremos el algoritmo de búsqueda binaria. La búsqueda es el proceso de encontrar algún elemento particular en la lista. Si el elemento está presente en la lista, entonces el proceso se considera exitoso y devuelve la ubicación de ese elemento. De lo contrario, la búsqueda se considera fallida.
La búsqueda lineal y la búsqueda binaria son las dos técnicas de búsqueda más populares. Aquí discutiremos el algoritmo de búsqueda binaria.
La búsqueda binaria es la técnica de búsqueda que funciona de manera eficiente en listas ordenadas. Por lo tanto, para buscar un elemento en alguna lista utilizando la técnica de búsqueda binaria, debemos asegurarnos de que la lista esté ordenada.
La búsqueda binaria sigue el enfoque de divide y vencerás en el que la lista se divide en dos mitades y el elemento se compara con el elemento central de la lista. Si se encuentra la coincidencia, se devuelve la ubicación del elemento intermedio. De lo contrario, buscamos en cualquiera de las mitades dependiendo del resultado del partido.
NOTA: La búsqueda binaria se puede implementar en elementos de matriz ordenados. Si los elementos de la lista no están ordenados, primero debemos ordenarlos.
Ahora, veamos el algoritmo de búsqueda binaria.
Algoritmo
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
Funcionamiento de la búsqueda binaria
Ahora, veamos el funcionamiento del algoritmo de búsqueda binaria.
Para comprender el funcionamiento del algoritmo de búsqueda binaria, tomemos una matriz ordenada. Será fácil entender el funcionamiento de la búsqueda binaria con un ejemplo.
Hay dos métodos para implementar el algoritmo de búsqueda binaria:
- método iterativo
- método recursivo
El método recursivo de búsqueda binaria sigue el enfoque de divide y vencerás.
Dejemos que los elementos de la matriz sean:
Deja que el elemento a buscar sea, k = 56
Tenemos que usar la siguiente fórmula para calcular el medio de la matriz -
mid = (beg + end)/2
Entonces, en la matriz dada -
mendigar = 0
fin = 8
medio = (0 + 8)/2 = 4. Entonces, 4 es la mitad de la matriz.
Ahora se encuentra el elemento a buscar. Entonces el algoritmo devolverá el índice del elemento coincidente.
Complejidad de la búsqueda binaria
Ahora, veamos la complejidad temporal de la búsqueda binaria en el mejor de los casos, el caso promedio y el peor de los casos. También veremos la complejidad espacial de la búsqueda binaria.
1. Complejidad del tiempo
| Caso | Complejidad del tiempo |
|---|---|
| Mejor caso | O(1) |
| Caso promedio | O(iniciar sesión) |
| Peor de los casos | O(iniciar sesión) |
2. Complejidad espacial
| Complejidad espacial | O(1) |
- La complejidad espacial de la búsqueda binaria es O (1).
Implementación de búsqueda binaria
Ahora veamos los programas de búsqueda binaria en diferentes lenguajes de programación.
Programa: Escriba un programa para implementar la búsqueda binaria en lenguaje C.
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> Producción
Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo.