Where is binary search used in practice?



Every programmer is taught that binary search is a good, fast way to search an ordered list of data. There are many toy textbook examples of using binary search, but what about in real programming: where is binary search actually used in real-life programs?


Posted 2009-02-12T05:28:27.160

Reputation: 266

4Where is plugging round pegs into round holes used in practice? – Svante – 2010-02-14T21:24:57.580

As I feel it's not emphasised enough in the top answers, I want to clarify that a binary search is used when your data is sorted. My most recent example was when checking if a given word was in a word list I knew to be sorted (because I sorted it myself earlier in the program). If your data isn't sorted, or can't be sorted, you can't trust the result of a binary search. – Andrew Martin – 2017-07-20T17:22:42.370



Binary search is used everywhere. Take any sorted collection from any language library (Java, .NET, C++ STL and so on) and they all will use (or have the option to use) binary search to find values. While true that you have to implement it rarely, you still have to understand the principles behind it to take advantage of it.

Grey Panther

Posted 2009-02-12T05:28:27.160

Reputation: 10 507


Binary search can be used to access ordered data quickly when memory space is tight. Suppose you want to store a set of 100.000 32-bit integers in a searchable, ordered data structure but you are not going to change the set often. You can trivially store the integers in a sorted array of 400.000 bytes, and you can use binary search to access it fast. But if you put them e.g. into a B-tree, RB-tree or whatever "more dynamic" data structure, you start to incur memory overhead. To illustrate, storing the integers in any kind of tree where you have left child and right child pointers would make you consume at least 1.200.000 bytes of memory (assuming 32-bit memory architecture). Sure, there are optimizations you can do, but that's how it works in general.

Because it is very slow to update an ordered array (doing insertions or deletions), binary search is not useful when the array changes often.

Here some practical examples where I have used binary search:

  • Implementing a "switch() ... case:" construct in a virtual machine where the case labels are individual integers. If you have 100 cases, you can find the correct entry in 6 to 7 steps using binary search, where as sequence of conditional branches takes on average 50 comparisons.
  • Doing fast substring lookup using suffix arrays, which contain all the suffixes of the set of searchable strings in lexiographic ordering (I wanted to conserve memory and keep the implementation simple)
  • Finding numerical solutions to an equation (when you are lazy and do not mind to implement Newton's method)

Antti Huima

Posted 2009-02-12T05:28:27.160

Reputation: 21 275

1About switch/case: Unless the cases are very sparse, the compiler will build a jump table instead. – kennytm – 2010-03-04T16:07:52.207


Every programmer needs to know how to use binary search when debugging.

When you have a program, and you know that a bug is visible at a particular point during the execution of the program, you can use binary search to pin-point the place where it actually happens. This can be much faster than single-stepping through large parts of the code.


Posted 2009-02-12T05:28:27.160


6Could you explain this more? I think I understand what you mean, but I would disagree that a human is applying binary search whenever a bug is found. – Polaris878 – 2009-08-07T15:21:48.503

I didn't say it is used always, or even that it must be used always. I said it's a necessary skill. – None – 2009-08-10T04:27:48.863

53How in the world did this become the top answer? – FogleBird – 2010-02-06T02:35:05.610

The question is where is binary search actually used in real-life "programs", not where is binary search actually used in real-life. – nawfal – 2014-06-13T09:42:37.883


Binary search is a good and fast way!

Before the arrival of STL and .NET framework, etc, you rather often could bump into situations where you needed to roll your own customized collection classes. Whenever a sorted array would be a feasible place of storing the data, binary search would be the way of locating entries in that array.

I'm quite sure binary search is in widespread use today as well, although it is taken care of "under the hood" by the library for your convenience.


Posted 2009-02-12T05:28:27.160

Reputation: 2 108


I've implemented binary searches in BTree implementations.

The BTree search algorithms were used for finding the next node block to read but, within the 4K block itself (which contained a number of keys based on the key size), binary search was used for find either the record number (for a leaf node) or the next block (for a non-leaf node).

Blindingly fast compared to sequential search since, like balanced binary trees, you remove half the remaining search space with every check.


Posted 2009-02-12T05:28:27.160

Reputation: 623 339


Answering your question with hands-on example.

In R programming language there is a package data.table. It is known from C-implemented, short syntax, high performance extension for data transformation. It uses binary search. Even without binary search it scales better than competitors.
You can find benchmark vs python pandas and vs R dplyr in project wiki grouping 2E9 - random order data.
There is also nice benchmark vs databases vs bigdata benchm-databases.

In recent data.table version (1.9.6) binary search was extended and now can be used as index on any atomic column.

I just found a nice summary with which I totally agree - see.

Anyone doing R comparisons should use data.table instead of data.frame. More so for benchmarks. data.table is the best data structure/query language I have found in my career. It's leading the way in The R world, and in my way, in all the data-focused languages.

So yes, binary search is being used and world is much better place thanks to it.


Posted 2009-02-12T05:28:27.160

Reputation: 7 233


We still use it heavily in our code to search thousands of ACLS many thousands of times a second. It's useful because the ACLs are static once they come in from file, and we can suffer the expense of growing the array as we add to it at bootup. Blazingly fast once its running too.

When you can search a 255 element array in at most 7 compare/jumps (511 in 8, 1023 in 9, etc) you can see that binary search is about as fast as you can get.

Adam Hawes

Posted 2009-02-12T05:28:27.160

Reputation: 5 030


I once implemented it (without even knowing that this was indeed binary search) for a GUI control showing two-dimensional data in a graph. Clicking with the mouse should set the data cursor to the point with the closest x value. When dealing with large numbers of points (several 1000, this was way back when x86 was only beginning to get over 100 MHz CPU frequency) this was not really usable interactively - I was doing a linear search from the start. After some thinking it occurred to me that I could approach this in a divide and conquer fashion. Took me some time to get it working under all edge cases.

It was only some time later that I learned that this is indeed a fundamental CS algorithm...


Posted 2009-02-12T05:28:27.160

Reputation: 29 850


Binary search can be used to debug with Git. It's called git bisect.

Sanghyun Lee

Posted 2009-02-12T05:28:27.160

Reputation: 8 920


Well, binary search is now used in 99% of 3D games and applications. Space is divided into a tree structure and a binary search is used to retrieve which subdivisions to display according to a 3D position and camera.

One of its first greatest showcase was Doom. Binary trees and associated search enhanced the rendering.


Posted 2009-02-12T05:28:27.160

Reputation: 19 508


One example is the stl set. The underlying data structure is a balanced binary search tree which supports look-up, insertion, and deletion in O(log n) due to binary search.

Another example is an integer division algorithm that runs in log time.


Posted 2009-02-12T05:28:27.160

Reputation: 16 163

Neither one was an example of binary search. – Antti Huima – 2009-02-12T17:27:31.083

Look-up in a balanced binary search tree repeatedly eliminates half of the remaining search space of a sorted collection. That's binary search.

To compute a/b without using "/" there's a loop that repeatedly doubles the value of an int until it's slightly too big. Again I'm doing binary search. – MrDatabase – 2009-02-13T01:55:19.007

@antii.huima, um... yes they both are. – Bob Somers – 2009-02-16T06:29:51.727

Actually, "binary search" is usually done on a sorted array. It is an algorithm. "binary search tree" is a data structure representing a binary search. – Bob Yoplait – 2010-11-25T18:56:07.183


Binary sort is useful in adjusting fonts to size of text with constant dimension of textbox

Marek Bardoński

Posted 2009-02-12T05:28:27.160

Reputation: 329


I had a program that iterated through a collection to perform some calculations. I thought that this was inefficient so I sorted the collection and then used a single binary search to find an item of interest. I returned this item and its matching neighbours. I had in-effect filtered the collection.

Doing this was actually slower than iterating the entire collection and fishing out matching items.

I continued to add items to the collection knowing that the sorting and searching performance would eventually catch up with the iteration. It took a collection of about 600 objects until the speed was identical. 1000 objects had a clear performance benefit.

I would also consider the type of data you are working with, the duplicates and spread. This will have an effect on the sorting and searching.

My answer is to try both methods and time them.


Posted 2009-02-12T05:28:27.160



It's the basis for hg bisect


Posted 2009-02-12T05:28:27.160

Reputation: 2 364


Amongst other places, I have an interpreter with a table of command names and a pointer to the function to interpret that command. There are about 60 commands. It would not be incredibly onerous to use a linear search - but I use a binary search.

Jonathan Leffler

Posted 2009-02-12T05:28:27.160

Reputation: 555 842


Semiconductor test programs used for measuring digital timing or analog levels make extensive use of binary search. Automatic Test Equipment (ATE) from Advantest, Teradyne, Verigy and the like can be thought of as truth table blasters, applying input logic and verifying output states of a digital part.

Think of a simple gate, with the input logic changing at time = 0 of each cycle, and transitioning X ns after the input logic changes. If you strobe the output before T=X,the logic does not match expected value. Strobe later than time T=X, and the logic does match expected value. Binary search is used to find the threshold between the latest value that the logic does not match, and the earliest part where it does.(A Teradyne FLEX system resolves timing to 39pS resolution, other testers are comparable). That's a simple way to measure transition time. Same technique can be used to solve for setup time, hold time, operable power supply levels, power supply vs. delay,etc.

Any kind of microprocessor, memory, FPGA, logic, and many analog mixed signal circuits use binary search in test and characterization.

-- mike


Posted 2009-02-12T05:28:27.160

Reputation: 21


I believe that the .NET SortedDictionary uses a binary tree behind the scenes (much like the STL map)... so a binary search is used to access elements in the SortedDictionary


Posted 2009-02-12T05:28:27.160

Reputation: 16 986


Python'slist.sort() method uses Timsort which (AFAIK) uses binary search to locate the positions of elements.


Posted 2009-02-12T05:28:27.160

Reputation: 18 897


Binary search offers a feature that many readymade map/dictionary implementations don't: finding non-exact matches.

For example, I've used binary search to implement geotagging of photos based on GPS logs: put all GPS waypoints in an array sorted by timestamp, and use binary search to identify the waypoint that lies closest in time to each photo's timestamp.

Michael Borgwardt

Posted 2009-02-12T05:28:27.160

Reputation: 291 858


Finding roots of an equation is probably one of those very easy things you want to do with a very easy algorithm like binary search.


Posted 2009-02-12T05:28:27.160

Reputation: 89 549


Delphi uses can enjoy binary search while searching string in sorted TStringList.

Michał Niklas

Posted 2009-02-12T05:28:27.160

Reputation: 38 953


If you have a set of elements to find in an array you can either search for each of them linearly or sort the array and then use binary search with the same comparison predicate. The latter is much faster.


Posted 2009-02-12T05:28:27.160

Reputation: 120 811

3Incorrect unless qualified with the following: May be faster if your number of lookups justifies the O (n log n) time required to sort the input. – DavidO – 2013-08-18T21:28:08.883