|
| 1 | +# Búsqueda binaria (un algoritmo de dividir y conquistar) |
| 2 | + |
| 3 | +#### Declaración de problema |
| 4 | + |
| 5 | +Dada una matriz ordenada de `n` elementos, escriba una función para buscar el índice de un elemento determinado (destino). |
| 6 | + |
| 7 | +#### Enfoque |
| 8 | + |
| 9 | +- Busque la matriz dividiendo la matriz por la mitad repetidamente. |
| 10 | +- Inicialmente, considere la matriz real y elija el elemento en el índice medio. |
| 11 | +- Mantener un índice más bajo, es decir, 0 y mayor índice, es decir, la longitud de la matriz. |
| 12 | +- Si es igual al elemento de destino, devuelva el índice. |
| 13 | +- De lo contrario, si es mayor que el elemento de destino, tenga en cuenta sólo la mitad izquierda de la matriz (índice inferior = 0, superior = medio - 1). |
| 14 | +- De lo contrario, si es menor que el elemento de destino, tenga en cuenta sólo la mitad derecha de la matriz (índice inferior = medio + 1, más alto = longitud de la matriz). |
| 15 | +- Devolver -1 si el elemento de destino no se encuentra en la matriz (caso base: si el índice inferior es mayor o igual que el índice superior). |
| 16 | + |
| 17 | +#### Complejidad horaria |
| 18 | + |
| 19 | +`O(log n)` Peor caso |
| 20 | +`O(1)` Mejor caso (Si el elemento central de la matriz inicial es el elemento de destino) |
| 21 | + |
| 22 | +#### Complejidad espacial |
| 23 | + |
| 24 | +O(1) Para enfoque iterativo |
| 25 | +O(log n) Para el enfoque recursivo debido a la pila de llamadas de recursividad |
| 26 | + |
| 27 | +#### Ejemplo |
| 28 | + |
| 29 | +``` |
| 30 | +arr = [1,2,3,4,5,6,7] |
| 31 | +
|
| 32 | +target = 2 |
| 33 | +Initially the element at middle index is 4 which is greater than 2. Therefore we search the left half of the |
| 34 | +array i.e. [1,2,3]. |
| 35 | +Here we find the middle element equal to target element so we return its index i.e. 1 |
| 36 | +
|
| 37 | +target = 9 |
| 38 | +Binary Search should return -1 as 9 is not present in the array |
| 39 | +``` |
| 40 | + |
| 41 | +#### Enlaces de implementación de código |
| 42 | + |
| 43 | +- [Java](https://github.com/TheAlgorithms/Java/blob/master/Searches/BinarySearch.java) |
| 44 | +- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Search/Binary%20Search.cpp) |
| 45 | +- [Python](https://github.com/TheAlgorithms/Python/blob/master/searches/binary_search.py) |
| 46 | +- [C-Sharp](https://github.com/TheAlgorithms/C-Sharp/blob/master/searches/binary_search.cs) |
| 47 | +- [C](https://github.com/TheAlgorithms/C/blob/master/searching/Binary_Search.c) |
| 48 | +- [JavaScript](https://github.com/TheAlgorithms/Javascript/blob/master/Search/BinarySearch.js) |
| 49 | +- [Haskell](https://github.com
A947
/TheAlgorithms/Haskell/blob/master/src/Misc/BinarySearch.hs) |
| 50 | +- [F-Sharp](https://github.com/TheAlgorithms/F-Sharp/blob/main/Algorithms/Search/BinarySearch.fs) |
| 51 | +- [Go](https://github.com/TheAlgorithms/Go/blob/master/searches/binarysearch.go) |
| 52 | +- [Rust](https://github.com/TheAlgorithms/Rust/blob/master/src/searching/binary_search.rs) |
| 53 | +- [Dart](https://github.com/TheAlgorithms/Dart/blob/master/search/binary_Search.dart) |
| 54 | +- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/Searches/binary_search.rb) |
| 55 | +- [PHP](https://github.com/TheAlgorithms/PHP/blob/master/searches/binary_search.php) |
| 56 | +- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/src/main/scala/Search/BinarySearch.scala) |
| 57 | +- [MATLAB-Octave](https://github.com/TheAlgorithms/MATLAB-Octave/blob/master/algorithms/Searching/binary_search.m) |
| 58 | + |
| 59 | +#### Explicación en video de YouTube |
| 60 | + |
| 61 | +[Un vídeo CS50 explicando el algoritmo de búsqueda binaria](https://www.youtube.com/watch?v=5xlIPT1FRcA) |
| 62 | + |
| 63 | +#### Explicación de animación |
| 64 | + |
| 65 | +- [Tute Board](https://boardhub.github.io/tute/?wd=binarySearchAlgo2) |
0 commit comments