Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , a binary search algorithm (or binary chop) is a technique for locating a particular value in a sorted list
Collation
Collation is the assembly of written information into a standard order. One common type of collation is called alphabetisation, though collation is not limited to ordering letters of the alphabet.... . The method makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the span (which, because the list is in sorted order, is the median
Median
In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.... value), comparing its value to the target value, and determining if it is greater than, less than, or equal to the target value.
Discussion
Ask a question about 'Binary search algorithm'
Start a new discussion about 'Binary search algorithm'
Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , a binary search algorithm (or binary chop) is a technique for locating a particular value in a sorted list
Collation
Collation is the assembly of written information into a standard order. One common type of collation is called alphabetisation, though collation is not limited to ordering letters of the alphabet.... . The method makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the span (which, because the list is in sorted order, is the median
Median
In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.... value), comparing its value to the target value, and determining if it is greater than, less than, or equal to the target value. A guessed index whose value turns out to be too high becomes the new upper bound of the span, and if its value is too low that index becomes the new lower bound. Only the sign of the difference is inspected: there is no attempt at an interpolation search
Interpolation search
Interpolation search is an algorithm for Search algorithm for a given key value in an indexed array that has been Collation by the values of the key.... based on the size of the difference. Pursuing this strategy iteratively, the method reduces the search span by a factor of two each time, and soon finds the target value or else determines that it is not in the list at all. A binary search is an example of a dichotomic
Dichotomic search
In computer science, a dichotomic search is a search algorithm that operates by selecting between two distinct alternatives at each step. It is a specific type of divide and conquer algorithm.... divide and conquer
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly.... search algorithm
Search algorithm
In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions.... .
Overview
Finding the index of a specific value in a sorted list
Sorting algorithm
In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a List in a certain Total order. The most-used orders are numerical order and lexicographical order.... is useful because, given the index, other data structures will contain associated information. Suppose a data structure containing the classic collection of name, address, telephone number and so forth has been accumulated, and an array is prepared containing the names, numbered from one to N. A query might be: what is the telephone number for a given name X. To answer this the array would be searched and the index (if any) corresponding to that name determined, whereupon the associated telephone number array would have Xs telephone number at that index, and likewise the address array and so forth. Appropriate provision must be made for the name not being in the list (typically by returning an index value of zero), indeed the question of interest might be only whether X is in the list or not.
If the list of names is in sorted order, a binary search will find a given name with far fewer probes than the simple procedure of probing each name in the list, one after the other in a linear search
Linear search
In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value.... , and the procedure is much simpler than organizing a hash table
Hash table
In computer science, a hash table, or a hash map, is a data structure that associates Unique key with value .The primary operation that hash functions support efficiently is a lookup: given a key , find the corresponding value .... . However, once created, searching with a hash table may well be faster, typically averaging just over one probe per lookup. With a non-uniform distribution of values, if it is known that some few items are much more likely to be sought for than the majority, then a linear search with the list ordered so that the most popular items are first may do better than binary search. The choice of the best method may not be immediately obvious. If, between searches, items in the list are modified or items are added or removed, maintaining the required organisation may consume more time than the searches.
Examples
Number guessing game
This rather simple game begins something like "I'm thinking of an integer between forty and sixty inclusive, and to your guesses I'll respond 'High', 'Low', or 'Yes!' as might be the case."
Supposing that N is the number of possible values (here, twenty-one as "inclusive" was stated), then at most questions are required to determine the number, since each question halves the search space. Note that one less question (iteration) is required than for the general algorithm, since the number is already constrained to be within a particular range.
Even if the number we're guessing can be arbitrarily large, in which case there is no upper bound N, we can still find the number in at most steps (where k is the (unknown) selected number) by first finding an upper bound by repeated doubling. For example, if the number were 11, we could use the following sequence of guesses to find it: 1, 2, 4, 8, 16, 12, 10, 11
One could also extend the technique to include negative numbers; for example the following guesses could be used to find -13: 0, -1, -2, -4, -8, -16, -12, -14, -13
Word lists
People typically use a mixture of the binary search and interpolative search algorithms when searching a telephone book, after the initial guess we exploit the fact that the entries are sorted and can rapidly find the required entry. For example when searching for Smith, if Rogers and Thomas have been found, one can flip to a page about halfway between the previous guesses. If this shows Samson, we know that Smith is somewhere between the Samson and Thomas pages so we can bisect these.
Computational complexity theory, as a branch of the theory of computation in computer science, investigates the problems related to the Computational resource required for the execution of algorithms , and the inherent difficulty in providing efficient algorithms for specific computational problems....
Even if we do not know a fixed range the number k falls in, we can still determine its value by asking simple yes/no questions of the form "Is k greater than x?" for some number x. As a simple consequence of this, if you can answer the question "Is this integer property k greater than a given value?" in some amount of time then you can find the value of that property in the same amount of time with an added factor of . This is called a reduction
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one computational problem into another problem.... , and it is because of this kind of reduction that most complexity theorists concentrate on decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.... s, algorithms that produce a simple yes/no answer.
For example, suppose we could answer "Does this n x n matrix have determinant
Determinant
In algebra, a determinant is a function depending on n that associates a scalar , det, to an n?n square matrix A. The fundamental geometric meaning of a determinant is a scale factor for measure when A is regarded as a linear transformation.... larger than k?" in O(n2) time. Then, by using binary search, we could find the (ceiling of the) determinant itself in O(n2log d) time, where d is the determinant; notice that d is not the size of the input, but the size of the output.
The method
In order to discuss the method in detail, a more formal description is necessary. The basic idea is that there is a data structure represented by array A in which individual elements are identified as A(1), A(2),…,A(N) and may be accessed in any order. The data structure contains a sub-element or data field called here Key, and the array is ordered so that the successive values A(1).Key = A(2).Key and so on. The requirement is that given some value x, find an index p (not necessarily the one and only) such that A(p).Key = x.
To begin with, the span to be searched is the full supplied list of elements, as marked by variables L and R, and their values are changed with each iteration of the search process, as depicted by the flowchart
Flowchart
A flowchart is common type of chart, that represents an algorithm or Process , showing the steps as boxes of various kinds, and their order by connecting these with arrows.... . Note that the division by two is integer division, with any remainder lost, so that 3/2 comes out as 1, not 1˝. The search finishes either because the value has been found, or else, the specified value is not in the list.
In Computer science, a predicate that, if true, will remain true throughout a specific sequence of Operation , is called invariant to that sequence.... of the array.
The initialisation of L and R to 0 and N + 1 make this merely a restatement of the supplied problem, that elements 1 to N are to be searched, so the notion is established to begin with. The first step of each iteration is to check that there is something to search, which is to say whether there are any elements in the search span (L + 1) to (R - 1). The number of such elements is (R - L - 1) so computing (R - L) gives (number of elements + 1); halving that number (with integer division) means that if there was one element (or more) then p = 1 (or more), but if none p = 0, and in that case the method terminates with the report "Not found". Otherwise, for p > 0, the search continues with p:=L + p, which by construction is within the bounds (L + 1) to (R - 1). That this position is at or adjacent to the middle of the span is not important here, merely that it is a valid choice.
Now compare x to A(p).Key. If x = A(p).Key then the method terminates in success. Otherwise, suppose x < A(p).Key. If so, then because the array is in sorted order, x will also be less than all later elements of the array, all the way to element (R - 1) as well. Accordingly, the value of the right-hand bound index R can be changed to be the value p, since, by the test just made, x < A(p).Key and so, if x is to be found, it will be amongst elements earlier than p, that is (p - 1) and earlier. And contrariwise, for the case x > A(p).Key, the value of L would be changed. Thus, whichever bound is changed the ruling notion is upheld, and further, the span remaining to be searched is reduced. If L is changed, it is changed to a higher number (at least L + 1), whereas if R is changed, it is to a lower number (at most R - 1) because those are the limits for p.
Should there have been just one value remaining in the search span (so that L + 1 = p = R - 1), and x did not match, then depending on the sign of the comparison either L or R will receive the value of p and at the start of the next iteration the span will be found to be empty.
Accordingly, with each iteration, if the search span is empty the result is "Not found", otherwise either x is found at the probe point p or the search span is reduced for the next iteration. Thus the method works, and so can be called an Algorithm
Algorithm
In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing.... .
That it is fast
After each iteration, the span left to be searched is roughly halved. If the original number of items is N = 2p, then after the first iteration there will be roughly 2p-1 items remaining, then roughly 2p-2, and so on. In the worst case, the algorithm must continue iterating until the span has been reduced to a single item, i.e. 20; this will have taken p = log2
Binary logarithm
In mathematics, the binary logarithm is the logarithm for base 2. It is the inverse function of .... (N) iterations. When compared to the linear search
Linear search
In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value.... , whose worst-case behaviour is N iterations, we see that the binary search is substantially faster as N grows large.
In most cases, N will not be an integer power of 2. In these cases, the worst-case iteration count will be ceil(log2(N)), where ceil denotes the ceiling function.
Average performance
There are two cases: for searches that will fail because the value is not in the list, the search span must be successively halved until no more elements remain and this process will require at most the p probes just defined, or one less. This latter occurs because the search span is not in fact exactly halved, and depending on the value of N and which elements of the list the absent value x is between, the span may be closed early.
For searches that will succeed because the value is in the list, the search may finish early because a probed value happens to match. Loosely speaking, half the time the search will finish one iteration short of the maximum and a quarter of the time, two early. Consider then a test in which a list of N elements is searched once for each of the N values in the list, and determine the number of probes n for all N searches.
In short is about the expected number of probes in an average successful search, and the worst case is , just one more probe. If the list is empty, no probes at all are made.
Suppose the list to be searched contains N even numbers (say, 2,4,6,8 for N = 4) and a search is done for values 1, 2, 3, 4, 5, 6, 7, 8, and 9. The even numbers will be found, and the average number of iterations can be calculated as described. In the case of the odd numbers, they will not be found, and the collection of test values probes every possible position (with regard to the numbers that are in the list) that they might be not found in, and an average is calculated. The maximum value is for each N the greatest number of iterations that were required amongst the various trail searches of those N elements. The first plot shows the iteration counts for N = 1 to 63 (with N = 1, all results are 1), and the second plot is for N = 1 to 32767.
The curve for the "found" searches approaches log2(N) − 1 more closely for larger N as larger numbers of iterations are involved, in the same way that the successive summations 1/2, 1/4 + 1/2, 1/8 + 1/4 + 1/2 approach 1 as the number of terms increases: these are the probabilities of early detection of equality in successive iterations of a search. The slight bend in the curves within each iteration limit group is due to the early narrowing of the search bounds into two sub-spans whose lengths are often unequal.
Thus binary search is a logarithmic algorithm and executes in O
Big O notation
In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.... time. In most cases it is considerably faster than a linear search
Linear search
In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value.... . It can be implemented using iteration
Iteration
Iteration means the act of repeating.... (as shown above), or recursion
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... . In some languages it is more elegantly expressed recursively; however, in some C-based languages tail recursion is not eliminated and the recursive version requires more stack space.
Binary search can interact poorly with the memory hierarchy (i.e. caching
Cache
In computer science, a cache is a collection of data duplicating original values stored elsewhere or computed earlier, where the original data is expensive to fetch or to compute, compared to the cost of reading the cache.... ), because of its random-access nature. For in-memory searching, if the span to be searched is small, a linear search may have superior performance simply because it exhibits better locality of reference. For external searching, care must be taken or each of the first several probes will lead to a disk seek. A common technique is to abandon binary searching for linear searching as soon as the size of the remaining span falls below a small value such as 8 or 16 or even more in recent computers. The exact value depends entirely on the machine running the algorithm.
Notice that for multiple searches with a fixed value for N, then (with the appropriate regard for integer division), the first iteration always selects the middle element at N/2, and the second always selects either N/4 or 3N/4, and so on. Thus if the array's key values are in some sort of slow storage (on a disc file, in virtual memory, not in the cpu's on-chip memory), keeping those three keys in a local array for a special preliminary search will avoid accessing widely separated memory. Escalating to seven or fifteen such values will allow further levels at not much cost in storage. On the other hand, if the searches are frequent and not separated by much other activity, the computer's various storage control features will more or less automatically promote frequently-accessed elements into faster storage.
When multiple binary searches are to be performed for the same key in related lists, fractional cascading
Fractional cascading
In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures.... can be used to speed up successive searches after the first one.
Extensions
There is no particular requirement that the array being searched has the bounds 1 to N. It is possible to search a specified range, elements first to last instead of 1 to N. All that is necessary is that the initialisation be L:=first - 1 and R:=last + 1, then all proceeds as before.
The elements of the list are not necessarily all unique. If one searches for a value that occurs multiple times in the list, the index returned will be of the first-encountered equal element, and this will not necessarily be that of the first, last, or middle element of the run of equal-key elements but will depend on the positions of the values. Modifying the list even in seemingly unrelated ways such as adding elements elsewhere in the list may change the result.
To find all equal elements an upward and downward linear search can be carried out from the initial result, stopping each search when the element is no longer equal. Thus, e.g. in a table of cities sorted by country, we can find all cities in a given country.
Several algorithms closely related to or extending binary search exist. For instance, noisy binary search solves the same class of projects as regular binary search, with the added complexity that any given test can return a false value at random. (Usually, the number of such erroneous results are bounded in some way, either in the form of an average error rate, or in the total number of errors allowed per element in the search space.) Optimal algorithms for several classes of noisy binary search problems have been known since the late seventies, and more recently, optimal algorithms for noisy binary search in quantum computers (where several elements can be tested at the same time) have been discovered.
Variations
There are many, and they are easily confused.
Exclusive or inclusive bounds
The most significant differences are between the "exclusive" and "inclusive" forms of the bounds. This description uses the "exclusive" bound form, that is the span to be searched is (L + 1) to (R - 1), and this may seem clumsy when the span to be searched could be described in the "inclusive" form, as L to R. This form may be attained by replacing all appearances of "L" by "(L - 1)" and "R" by "(R + 1)" then rearranging. Thus, the initialisation of L:=0 becomes (L - 1):=0 or L:=1, and R:=N + 1 becomes (R + 1):=N + 1 or R:=N. So far so good, but note now that the changes to L and R are no longer simply transferring the value of p to L or R as appropriate but now must be (R + 1):=p or R:=p - 1, and (L - 1):=p or L:=p + 1.
Thus, the gain of a simpler initialisation, done once, is lost by a more complex calculation, and which is done for every iteration. If that is not enough, the test for an empty span is more complex also, as compared to the simplicity of checking that the value of p is zero. Nevertheless, this is the form found in many publications, such as Donald Knuth
Donald Knuth
Donald Ervin Knuth is a renowned computer science and Emeritus of the Art of Computer Programming at Stanford University.Author of the seminal multi-volume work The Art of Computer Programming , Knuth has been called the "father" of the run-time analysis, contributing to the development of, and systematizing formal mathematical techn... . The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition.
Locate the middle in one step
The other main variation is to combine the two step calculation of the probe position into one step, that is, p:=(R - L)/2; p:=p + L; into p:=(L + R)/2; which is indeed less work, but when the check for an empty search space is incorporated, the saving is lost because rather than if p <= 0 (which tests the just-computed value of p directly) the test becomes if p <= L and this second form requires the subtraction of the value of L. Pseudo machine code should read somewhat as follows:
Load R
Subtract L
IntDiv 2 Do not store this intermediate result into p yet.
JumpZN NotFound if result is Zero or Negative, Jump to NotFound.
AddL
Store p
That is, the (human) compiler has recognised that in the three statements p:=(R - L)/2; if p <= 0 return(-L); p:=p + L; the value of p is already in the working register and need not be stored and retrieved until the end where it is stored once. The two-statement version, p:=(L + R)/2; if p <= L return(-L); would become
Load L
AddR
IntDiv 2
Store p Thus p:=(L + R)/2;
Subtract L Compare p to L for if p <= L
JumpZN NotFound
This version has the slight disadvantages of an unnecessary store to p if NotFound and that the value of p is no longer in the working register ready to be used to index the array in A(p).Key of the next statement, but ordinarily it will involve the same number of actions, though computer compilers may not produce such code. Thus a tie: there is no advantage in locating the middle in one step, indeed the preference would be for the three-statement form. However there is a very good reason not to use the two-statement form, due to the risk of overflow described below.
Deferred detection of equality
Because of the syntax difficulties discussed below, so that distinguishing the three states <, =, and > would have to be done with two comparisons, it is possible to use just one comparison and at the end when the span is reduced to zero, equality can be tested for. The example distinguishes only < from >=.
Midpoint and width
An entirely different variation involves abandoning the L and R pointers in favour of a current position p and a width w where at each iteration, p is adjusted by + or - w and w is halved. Professor Knuth remarks "It is possible to do this, but only if extreme care is paid to the details" – Section 6.2.1, page 414 of The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition, outlines an algorithm, with the further remark "Simpler approaches are doomed to failure!"
Computer usage
The algorithm
"Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" — Professor Donald Knuth
Donald Knuth
Donald Ervin Knuth is a renowned computer science and Emeritus of the Art of Computer Programming at Stanford University.Author of the seminal multi-volume work The Art of Computer Programming , Knuth has been called the "father" of the run-time analysis, contributing to the development of, and systematizing formal mathematical techn...
Jon Louis Bentley is a researcher in the field of computer science. Bentley worked on his MS and Ph.D at the University of North Carolina at Chapel Hill before eventually becoming a Professor of Computer Science and Mathematics at Carnegie-Mellon University.... assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks (Kruse, 1999). Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.
Numerical difficulties
In a practical implementation, the variables used to represent the indices will be of finite size, hence only capable of representing a finite range of values. For example, 16-bit unsigned integers
Signedness
In computing, signedness is a property of variables representing numbers in computer programs. A numeric variable is signed if it can represent both negative and non-negative numbers, and unsigned if it can only represent positive numbers.... can only hold values from 0 to 65535. If the binary search algorithm is to operate on large arrays, this has two implications:
The values first - 1 and last + 1 must both be representable. Therefore, continuing the 16-bit example, the largest value that last may take is +65534, not +65535. A problem exists even for the "inclusive" form of the method, as if x > A(65535).Key, then on the final iteration the algorithm will attempt to store 65536 into L and fail. Equivalent issues apply to the lower limit.
If the midpoint of the span is calculated as p := (L + R)/2, then the value (L + R) will exceed the number range if last is greater than (in our example) 65535/2 and the search wanders toward the upper end of the search space. This can be avoided by performing the calculation as p := L + (R - L)/2.
Syntax difficulties
Another difficulty is presented by the absence in most computer languages of a three-way result from a comparison, which forces a comparison to be performed twice. The form is somewhat as follows:
if a < b then action1
else if a > b then action2
else action3;
About half the time, the first test will be true so that there will be only one comparison of a and b, but the other half of the time it will be false, and a second comparison forced. This is so grievous that some versions are recast so as not to make a second test at all thus not determining equality until the span has been reduced to zero, and thereby foregoing the possibility of early termination – remember that about half the time the search will happen on a matching value one iteration short of the limit.
It is quite easy to make this problem still worse (e.g. as in ) by using an order such as
if a = b then action3
else if a > b then action2
else action1;
Rather than detecting equality early (as it might appear to), this will force two comparisons to be performed for all but the last iteration of a search.
Niklaus Emil Wirth is a Switzerland computer science, best known for designing several programming languages, including Pascal , and for pioneering several classic topics in software engineering.... recorded this algorithm in Standard Pascal
Pascal (programming language)
Pascal is an influential imperative programming and Procedural programming programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structure.... :
i := 1;
j := n;
repeat
k := (i+j) div 2;
if x > A[k] then
i := k+1
else
j := k-1;
until (A[k]=x) or (i>j);
Fortran is a general-purpose programming language, procedural programming language, imperative programming language programming language that is especially suited to numerical analysis and scientific computing.... does offer a three-way test, here is a version for searching an array of floating-point numbers. For labels Fortran uses numbers at the start of statements, thus the 1, 2, 3, and 4. The if statement performs a go to to one of the three nominated labels according to the sign of its arithmetic expression.
Recursive
The most straightforward implementation is recursive, which recursively searches the subrange dictated by the comparison:
It is invoked with initial low and high values of 0 and N-1. We can eliminate the tail recursion
Tail recursion
In computer science, tail recursion is a special case of Recursion_ in which the last operation of the function, the tail call, is a recursive call.... above and convert this to an iterative implementation:
In computer science, a three-way comparison takes two values A and B belonging to a type with a total order and determines whether A B in a single operation, in accordance with the mathematical trichotomy .... , the required three-way comparison has to be replaced by two two-way comparisons that would on average involve one and a half comparisons per iteration, not one. To reduce this overhead, some implementations defer checking for equality until after the search completes, as in this pseudocode:
This approach foregoes the possibility of early termination on discovery of a match, that for successful searches reduces the expected running time from log2(N) to log2(N) − 1. On the other hand, as N increases, 1·5(log2(N) − 1) exceeds log2(N) by an ever-increasing margin.
Language support
Many standard libraries provide a way to do a binary search. C
C (programming language)
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... provides in its standard library. C++
C++
C++ is a general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level programming language and low-level programming language language features.... 's STL
Standard Template Library
The Standard Template Library is a Library partially included in the C++ C++ standard library. It provides Container s, iterators, algorithms, and Function objects.... provides algorithm functions binary_search, lower_bound and upper_bound. Java
Java (Sun)
Java refers to a number of computer software products and specifications from Sun Microsystems that together provide a system for developing application software and deploying it in a cross-platform environment.... offers a set of overloaded binarySearch static methods in the classes and for performing binary searches on Java arrays and Lists, respectively. They must be arrays of primitives, or the arrays or Lists must be of a type that implements the Comparable interface, or you must specify a custom Comparator object. Microsoft
Microsoft
Microsoft Corporation is a multinational corporation computer technology corporation that develops, manufactures, licenses, and supports a wide range of computer software products for computing devices.... 's .NET Framework 2.0 offers static generic
Generic programming
Generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters and was pioneered by Ada which appeared in 1983.... versions of the Binary Search algorithm in its collection base classes. An example would be System.Array's method BinarySearch(T[] array, T value).Python
Python (programming language)
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python's core syntax and semantics are Minimalism , while the standard library is large and comprehensive.... provides the module. COBOL
COBOL
COBOL is one of the oldest programming languages still in active use. Its name is an acronym for COmmon Business-Oriented Language, defining its primary domain in business, finance, and administrative systems for companies and governments.... can perform binary search on internal tables using the SEARCH ALL statement. Perl
Perl
In computer programming, Perl is a high-level programming language, List of programming languages by category, Interpreter , dynamic programming language.... can perform a generic binary search using the CPAN
CPAN
CPAN, the Comprehensive Perl Archive Network, is an archive of over 14,800 modules of software written in Perl, as well as documentation for it.... module .
In computer science, an index can be:# an integer which identifies an array element# a pointer data element.# a data structure that enables sublinear-time lookup... Very fast 'lookup' using an index to directly select an entry
In computer programming, a branch table is a term used to describe an efficient method of transferring program control to another part of a program using a table of branch Instruction s.... s Alternative indexed 'lookup' technique for decision making
In computer science, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically....
Run-time analysis, illustrating binary search technique on machines of differing speeds
External links
.NET Framework Class Library Array.BinarySearch Generic Method (T[], T)
