¿Cómo es la búsqueda binaria frente a otros esquemas de búsqueda?
Las matrices ordenadas con búsqueda binaria son una solución muy poco eficiente cuando las operaciones de inserción y borrado se intercalan con la recuperación, lo que lleva

O(n) por cada operación de este tipo. Además, las matrices ordenadas pueden complicar el uso de la memoria, sobre todo cuando los elementos se insertan a menudo en la matriz. Hay otras estructuras de datos que admiten inserciones y eliminaciones mucho más eficientes. La búsqueda binaria puede utilizarse para realizar correspondencias exactas y pertenencia a conjuntos (determinar si un valor objetivo está en una colección de valores). Existen estructuras de datos que permiten realizar más rápidamente la correspondencia exacta y la pertenencia a conjuntos. Sin embargo, a diferencia de muchos otros esquemas de búsqueda, la búsqueda binaria puede utilizarse para realizar correspondencias aproximadas eficientes, que suelen realizarse en tiempo
O(log n) independientemente del tipo o estructura de los propios valores. Además, hay algunas operaciones, como encontrar el elemento más pequeño y el más grande, que pueden realizarse eficientemente en una matriz ordenada.

Búsqueda lineal:

La búsqueda lineal es un algoritmo de búsqueda simple que comprueba cada registro hasta encontrar el valor objetivo. La búsqueda lineal puede realizarse en una lista enlazada, que permite insertar y borrar más rápidamente que una matriz. La búsqueda binaria es más rápida que la búsqueda lineal para matrices ordenadas, excepto si la matriz es corta, aunque la matriz debe ordenarse previamente. Todos los algoritmos de ordenación basados en la comparación de elementos, como el quicksort y el merge sort, requieren al menos
O(nlog n) comparaciones en el peor de los casos. A diferencia de la búsqueda lineal, la búsqueda binaria puede utilizarse para realizar comparaciones aproximadas eficientes. Hay operaciones, como encontrar el elemento más pequeño y el más grande, que pueden hacerse de forma eficiente en una matriz ordenada, pero no en una matriz sin ordenar.

Árboles:

Los árboles de búsqueda binaria se buscan utilizando un algoritmo similar al de la búsqueda binaria.
Un árbol de búsqueda binario es una estructura de datos en forma de árbol binario que funciona según el principio de la búsqueda binaria. Los registros del árbol están ordenados, y cada registro del árbol puede buscarse utilizando un algoritmo similar a la búsqueda binaria, que requiere un tiempo medio logarítmico. La inserción y la eliminación también requieren un tiempo medio logarítmico en los árboles de búsqueda binaria. Esto puede ser más rápido que la inserción y eliminación en tiempo lineal de las matrices ordenadas, y los árboles binarios conservan la capacidad de realizar todas las operaciones posibles en una matriz ordenada, incluidas las consultas de rango y aproximación.

Sin embargo, la búsqueda binaria suele ser más eficaz para buscar, ya que lo más probable es que los árboles de búsqueda binaria estén imperfectamente equilibrados, lo que da lugar a un rendimiento ligeramente peor que la búsqueda binaria. Esto se aplica incluso a los árboles de búsqueda binaria equilibrados, árboles de búsqueda binaria que equilibran sus propios nodos, porque rara vez producen el árbol con el menor número de niveles posible. Excepto en el caso de los árboles de búsqueda binaria equilibrados, el árbol puede estar muy desequilibrado, con pocos nodos internos con dos hijos, lo que hace que el tiempo de búsqueda medio y en el peor de los casos se aproxime a
n comparaciones. Los árboles de búsqueda binarios ocupan más espacio que las matrices ordenadas.

Los árboles de búsqueda binarios se prestan a la búsqueda rápida en memoria externa almacenada en discos duros, ya que los árboles de búsqueda binarios pueden estructurarse eficazmente en sistemas de archivos. El árbol B generaliza este método de organización de árboles. Los árboles B se utilizan con frecuencia para organizar el almacenamiento a largo plazo, como bases de datos y sistemas de archivos.

Hashing:
Para implementar matrices asociativas, las tablas hash, una estructura de datos que asigna claves a registros mediante una función hash, suelen ser más rápidas que la búsqueda binaria en una matriz ordenada de registros.La mayoría de las implementaciones de tablas hash sólo requieren un tiempo constante amortizado de media.Sin embargo, el hashing no es útil para las coincidencias aproximadas, como calcular la siguiente clave más pequeña, la siguiente más grande y la más cercana, ya que la única información que se da en una búsqueda fallida es que el objetivo no está presente en ningún registro. La búsqueda binaria es ideal para este tipo de coincidencias, ya que las realiza en tiempo logarítmico. La búsqueda binaria también admite coincidencias aproximadas. Algunas operaciones, como encontrar el elemento más pequeño y el más grande, pueden realizarse de forma eficiente en matrices ordenadas, pero no en tablas hash.

Algoritmos de pertenencia a conjuntos:
Un problema relacionado con la búsqueda es la pertenencia a conjuntos. Cualquier algoritmo que realice búsquedas, como la búsqueda binaria, también puede utilizarse para la pertenencia a conjuntos. Hay otros algoritmos que se adaptan más específicamente a la pertenencia a conjuntos. Una matriz de bits es el más sencillo, útil cuando el rango de claves es limitado. Almacena de forma compacta una colección de bits, en la que cada bit representa una única clave dentro del rango de claves. Las matrices de bits son muy rápidas, sólo requieren un tiempo O(1).
El tipo de matriz Judy1 maneja eficazmente claves de 64 bits.

Para obtener resultados aproximados, los filtros de Bloom, otra estructura de datos probabilística basada en el hash, almacenan un conjunto de claves codificándolas mediante una matriz de bits y múltiples funciones hash. Los filtros de Bloom ocupan mucho menos espacio que las matrices de bits en la mayoría de los casos y no son mucho más lentos: con
k funciones hash, las consultas de pertenencia sólo requieren
 O(k) de tiempo. Sin embargo, los filtros de Bloom adolecen de falsos positivos.

Otras estructuras de datos:
Existen estructuras de datos que pueden mejorar la búsqueda binaria en algunos casos, tanto para las búsquedas como para otras operaciones disponibles para las matrices ordenadas. Por ejemplo, las búsquedas, las coincidencias aproximadas y las operaciones disponibles para las matrices ordenadas pueden realizarse con más eficacia que la búsqueda binaria en estructuras de datos especializadas, como los árboles de van Emde Boas, los árboles de fusión, los tries y las matrices de bits. Estas estructuras de datos especializadas sólo suelen ser más rápidas porque aprovechan las propiedades de las claves con un determinado atributo (normalmente claves que son números enteros pequeños), por lo que consumirán mucho tiempo o espacio para las claves que carezcan de ese atributo. Siempre que las claves puedan ordenarse, estas operaciones siempre pueden realizarse al menos eficientemente en una matriz ordenada, independientemente de las claves. Algunas estructuras, como las matrices Judy, utilizan una combinación de enfoques para mitigar esto, conservando la eficiencia y la capacidad de realizar correspondencias aproximadas.
Las matrices ordenadas con la búsqueda binaria son una solución muy ineficiente cuando las operaciones de inserción y borrado se intercalan con la recuperación. Además, las matrices ordenadas pueden complicar el uso de la memoria, sobre todo cuando los elementos se insertan a menudo en la matriz.
La búsqueda binaria es más rápida que la búsqueda lineal para matrices ordenadas, excepto si la matriz es corta, aunque la matriz debe ordenarse previamente.
La búsqueda binaria suele ser más eficaz para buscar, ya que lo más probable es que los árboles de búsqueda binaria estén imperfectamente equilibrados, lo que da lugar a un rendimiento ligeramente peor que la búsqueda binaria.
una estructura de datos que asigna claves a registros mediante una función hash, suele ser más rápida que la búsqueda binaria en una matriz ordenada de registros.
How is binary search vs other searching schemes?
Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking 

O(n) time for each such operation. In addition, sorted arrays can complicate memory use especially when elements are often inserted into the array. There are other data structures that support much more efficient insertion and deletion. Binary search can be used to perform exact matching and set membership (determining whether a target value is in a collection of values). There are data structures that support faster exact matching and set membership. However, unlike many other searching schemes, binary search can be used for efficient approximate matching, usually performing such matches in 
O(log n) time regardless of the type or structure of the values themselves. In addition, there are some operations, like finding the smallest and largest element, that can be performed efficiently on a sorted array.

Linear search:

Linear search is a simple search algorithm that checks every record until it finds the target value. Linear search can be done on a linked list, which allows for faster insertion and deletion than an array. Binary search is faster than linear search for sorted arrays except if the array is short, although the array needs to be sorted beforehand. All sorting algorithms based on comparing elements, such as quicksort and merge sort, require at least 
O(nlog n) comparisons in the worst case. Unlike linear search, binary search can be used for efficient approximate matching. There are operations such as finding the smallest and largest element that can be done efficiently on a sorted array but not on an unsorted array.

Trees:

Binary search trees are searched using an algorithm similar to binary search.
A binary search tree is a binary tree data structure that works based on the principle of binary search. The records of the tree are arranged in sorted order, and each record in the tree can be searched using an algorithm similar to binary search, taking on average logarithmic time. Insertion and deletion also require on average logarithmic time in binary search trees. This can be faster than the linear time insertion and deletion of sorted arrays, and binary trees retain the ability to perform all the operations possible on a sorted array, including range and approximate queries.

However, binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search. This even applies to balanced binary search trees, binary search trees that balance their own nodes, because they rarely produce the tree with the fewest possible levels. Except for balanced binary search trees, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching 
n comparisons.[e] Binary search trees take more space than sorted arrays.

Binary search trees lend themselves to fast searching in external memory stored in hard disks, as binary search trees can be efficiently structured in filesystems. The B-tree generalizes this method of tree organization. B-trees are frequently used to organize long-term storage such as databases and filesystems.

Hashing:
For implementing associative arrays, hash tables, a data structure that maps keys to records using a hash function, are generally faster than binary search on a sorted array of records.Most hash table implementations require only amortized constant time on average.However, hashing is not useful for approximate matches, such as computing the next-smallest, next-largest, and nearest key, as the only information given on a failed search is that the target is not present in any record. Binary search is ideal for such matches, performing them in logarithmic time. Binary search also supports approximate matches. Some operations, like finding the smallest and largest element, can be done efficiently on sorted arrays but not on hash tables.

Set membership algorithms:
A related problem to search is set membership. Any algorithm that does lookup, like binary search, can also be used for set membership. There are other algorithms that are more specifically suited for set membership. A bit array is the simplest, useful when the range of keys is limited. It compactly stores a collection of bits, with each bit representing a single key within the range of keys. Bit arrays are very fast, requiring only 
O(1) time.The Judy1 type of Judy array handles 64-bit keys efficiently.

For approximate results, Bloom filters, another probabilistic data structure based on hashing, store a set of keys by encoding the keys using a bit array and multiple hash functions. Bloom filters are much more space-efficient than bit arrays in most cases and not much slower: with 
k hash functions, membership queries require only 
 O(k) time. However, Bloom filters suffer from false positives.

Other data structures:
There exist data structures that may improve on binary search in some cases for both searching and other operations available for sorted arrays. For example, searches, approximate matches, and the operations available to sorted arrays can be performed more efficiently than binary search on specialized data structures such as van Emde Boas trees, fusion trees, tries, and bit arrays. These specialized data structures are usually only faster because they take advantage of the properties of keys with a certain attribute (usually keys that are small integers), and thus will be time or space consuming for keys that lack that attribute. As long as the keys can be ordered, these operations can always be done at least efficiently on a sorted array regardless of the keys. Some structures, such as Judy arrays, use a combination of approaches to mitigate this while retaining efficiency and the ability to perform approximate matching.
Sorted arrays with the binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval. In addition, sorted arrays can complicate memory use especially when elements are often inserted into the array.
Binary search is faster than linear search for sorted arrays except if the array is short, although the array needs to be sorted beforehand.
Binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search.
a data structure that maps keys to records using a hash function, is generally faster than binary search on a sorted array of records.