Qu'en est-il de la recherche binaire par rapport à d'autres systèmes de recherche ?
Les tableaux triés avec recherche binaire sont une solution très inefficace lorsque les opérations d'insertion et de suppression sont intercalées avec la recherche, ce qui prend

O(n) pour chacune de ces opérations. En outre, les tableaux triés peuvent compliquer l'utilisation de la mémoire, en particulier lorsque des éléments sont souvent insérés dans le tableau. Il existe d'autres structures de données qui permettent une insertion et une suppression beaucoup plus efficaces. La recherche binaire peut être utilisée pour effectuer une correspondance exacte et une appartenance à un ensemble (déterminer si une valeur cible fait partie d'une collection de valeurs). Il existe des structures de données qui permettent d'effectuer plus rapidement des correspondances exactes et des appartenances à des ensembles. Toutefois, contrairement à de nombreux autres schémas de recherche, la recherche binaire peut être utilisée pour effectuer une correspondance approximative efficace, généralement en un temps
O(log n), quel que soit le type ou la structure des valeurs elles-mêmes. En outre, certaines opérations, comme la recherche du plus petit et du plus grand élément, peuvent être effectuées efficacement sur un tableau trié.

Recherche linéaire :

La recherche linéaire est un algorithme de recherche simple qui vérifie chaque enregistrement jusqu'à ce qu'il trouve la valeur cible. La recherche linéaire peut être effectuée sur une liste chaînée, qui permet des insertions et des suppressions plus rapides qu'un tableau. La recherche binaire est plus rapide que la recherche linéaire pour les tableaux triés, sauf si le tableau est court, bien que le tableau doive être trié au préalable. Tous les algorithmes de tri basés sur la comparaison d'éléments, tels que le tri rapide et le tri par fusion, nécessitent au moins
O(nlog n) comparaisons dans le pire des cas. Contrairement à la recherche linéaire, la recherche binaire peut être utilisée pour une correspondance approximative efficace. Certaines opérations, telles que la recherche du plus petit et du plus grand élément, peuvent être effectuées efficacement sur un tableau trié, mais pas sur un tableau non trié.

Les arbres :

Les arbres de recherche binaire sont recherchés à l'aide d'un algorithme similaire à la recherche binaire.
Un arbre de recherche binaire est une structure de données binaire qui fonctionne selon le principe de la recherche binaire. Les enregistrements de l'arbre sont classés par ordre, et chaque enregistrement de l'arbre peut être recherché à l'aide d'un algorithme similaire à la recherche binaire, ce qui prend en moyenne un temps logarithmique. L'insertion et la suppression nécessitent également un temps logarithmique moyen dans les arbres de recherche binaire. Cela peut être plus rapide que l'insertion et la suppression en temps linéaire de tableaux triés, et les arbres binaires conservent la possibilité d'effectuer toutes les opérations possibles sur un tableau trié, y compris l'intervalle et les requêtes approximatives.

Toutefois, la recherche binaire est généralement plus efficace pour la recherche, car les arbres de recherche binaire seront très probablement imparfaitement équilibrés, ce qui se traduira par des performances légèrement inférieures à celles de la recherche binaire. Cela s'applique même aux arbres de recherche binaire équilibrés, c'est-à-dire aux arbres de recherche binaire qui équilibrent leurs propres nœuds, car ils produisent rarement l'arbre avec le moins de niveaux possibles. À l'exception des arbres de recherche binaire équilibrés, l'arbre peut être gravement déséquilibré avec peu de nœuds internes ayant deux enfants, ce qui fait que le temps de recherche moyen et le temps de recherche dans le pire des cas s'approchent de
n comparaisons. Les arbres de recherche binaires prennent plus de place que les tableaux triés.

Les arbres de recherche binaires se prêtent à une recherche rapide dans la mémoire externe stockée sur les disques durs, car les arbres de recherche binaires peuvent être structurés efficacement dans les systèmes de fichiers. L'arbre B généralise cette méthode d'organisation des arbres. Les arbres B sont fréquemment utilisés pour organiser le stockage à long terme, comme les bases de données et les systèmes de fichiers.

Hachage :
Pour la mise en œuvre de tableaux associatifs, les tables de hachage, une structure de données qui associe des clés à des enregistrements à l'aide d'une fonction de hachage, sont généralement plus rapides que la recherche binaire sur un tableau trié d'enregistrements.La plupart des mises en œuvre de tables de hachage ne nécessitent qu'un temps constant amorti en moyenne.Toutefois, le hachage n'est pas utile pour les correspondances approximatives, telles que le calcul de la plus petite clé suivante, de la plus grande clé suivante et de la clé la plus proche, car la seule information donnée lors d'une recherche infructueuse est que la cible n'est pas présente dans un enregistrement. La recherche binaire est idéale pour de telles correspondances, car elle les effectue en un temps logarithmique. La recherche binaire prend également en charge les correspondances approximatives. Certaines opérations, comme la recherche du plus petit et du plus grand élément, peuvent être effectuées efficacement sur des tableaux triés, mais pas sur des tables de hachage.

Algorithmes d'appartenance à un ensemble :
L'appartenance à un ensemble est un problème connexe à la recherche. Tout algorithme qui effectue des recherches, comme la recherche binaire, peut également être utilisé pour l'appartenance à un ensemble. D'autres algorithmes sont plus spécifiquement adaptés à l'appartenance à un ensemble. Le tableau de bits est le plus simple, utile lorsque la gamme de clés est limitée. Il stocke de manière compacte une collection de bits, chaque bit représentant une clé unique dans l'intervalle des clés. Les tableaux de bits sont très rapides, puisqu'ils ne requièrent qu'un temps O(1).
Le type Judy1 de tableau Judy gère efficacement les clés de 64 bits.

Pour des résultats approximatifs, les filtres de Bloom, une autre structure de données probabiliste basée sur le hachage, stockent un ensemble de clés en les codant à l'aide d'un tableau de bits et de plusieurs fonctions de hachage. Dans la plupart des cas, les filtres de Bloom sont beaucoup moins encombrants que les tableaux de bits et ne sont pas beaucoup plus lents : avec
k fonctions de hachage, les requêtes d'appartenance ne prennent que
 O(k). Cependant, les filtres de Bloom souffrent de faux positifs.

Autres structures de données :
Il existe des structures de données qui peuvent améliorer la recherche binaire dans certains cas, tant pour la recherche que pour d'autres opérations disponibles pour les tableaux triés. Par exemple, les recherches, les correspondances approximatives et les opérations disponibles pour les tableaux triés peuvent être effectuées plus efficacement que la recherche binaire sur des structures de données spécialisées telles que les arbres de van Emde Boas, les arbres de fusion, les essais et les tableaux de bits. Ces structures de données spécialisées ne sont généralement plus rapides que parce qu'elles tirent parti des propriétés des clés dotées d'un certain attribut (généralement les clés qui sont de petits nombres entiers), et seront donc plus longues ou plus encombrantes pour les clés dépourvues de cet attribut. Tant que les clés peuvent être ordonnées, ces opérations peuvent toujours être effectuées au moins efficacement sur un tableau trié, quelles que soient les clés. Certaines structures, telles que les tableaux de Judy, utilisent une combinaison d'approches pour atténuer ce problème tout en conservant l'efficacité et la possibilité d'effectuer des correspondances approximatives.
Les tableaux triés avec la recherche binaire sont une solution très inefficace lorsque les opérations d'insertion et de suppression sont intercalées avec la récupération. En outre, les tableaux triés peuvent compliquer l'utilisation de la mémoire, en particulier lorsque des éléments sont souvent insérés dans le tableau.
La recherche binaire est plus rapide que la recherche linéaire pour les tableaux triés, sauf si le tableau est court, bien que le tableau doive être trié au préalable.
La recherche binaire est généralement plus efficace pour la recherche, car les arbres de recherche binaire seront très probablement imparfaitement équilibrés, ce qui se traduira par des performances légèrement inférieures à celles de la recherche binaire.
une structure de données qui associe des clés à des enregistrements à l'aide d'une fonction de hachage, est généralement plus rapide que la recherche binaire sur un tableau d'enregistrements triés.
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.