Where is binary search used in practice?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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...

Answer 10

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

Answer 11

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)

Answer 12

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.

Answer 13

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

Answer 14

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.

Answer 15

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

Answer 16

May be these links can help to illustrate the power of binary search trees (code is in java)

http://www.technicalypto.com/2010/01/binary-search-trees-in-java.html

http://www.technicalypto.com/2010/02/binary-search-trees-in-java-continued.html

Answer 17

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

Answer 18

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.

Answer 19

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.

Answer 20

Ask google:

http://www.google.com/codesearch?hl=en&lr=&q=%22binary+search%22&sbtn=Search

As of now it found about 39,100 mentions of "binary search".

Answer 21

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

became the top answer because in writing a program which uses binary search once, you probably used it yourself in debugging (albeit as a human) many times...

(Apologies for placement, too new to comment.)

Answer 22

It's the basis for hg bisect