Performance
With each test that fails to find a match at the probed position, the search is continued with one or other of the two sub-intervals, each at most half the size. More precisely, if the number of items, N, is odd then both sub-intervals will contain (N - 1)/2 elements, while if N is even then the two sub-intervals contain N/2 - 1 and N/2 elements.
If the original number of items is N then after the first iteration there will be at most N/2 items remaining, then at most N/4 items, at most N/8 items, and so on. In the worst case, when the value is not in the list, the algorithm must continue iterating until the span has been made empty; this will have taken at most ⌊log2(N) + 1⌋ iterations, where the ⌊ ⌋ notation denotes the floor function that rounds its argument down to an integer. This worst case analysis is tight: for any N there exists a query that takes exactly ⌊log2(N) + 1⌋ iterations. When compared to linear search, whose worst-case behaviour is N iterations, we see that binary search is substantially faster as N grows large. For example, to search a list of one million items takes as many as one million iterations with linear search, but never more than twenty iterations with binary search. However, a binary search can only be performed if the list is in sorted order.
Read more about this topic: Binary Search Algorithm
Famous quotes containing the word performance:
“No performance is worth loss of geniality. ‘Tis a cruel price we pay for certain fancy goods called fine arts and philosophy.”
—Ralph Waldo Emerson (1803–1882)
“True balance requires assigning realistic performance expectations to each of our roles. True balance requires us to acknowledge that our performance in some areas is more important than in others. True balance demands that we determine what accomplishments give us honest satisfaction as well as what failures cause us intolerable grief.”
—Melinda M. Marshall (20th century)
“The way to go to the circus, however, is with someone who has seen perhaps one theatrical performance before in his life and that in the High School hall.... The scales of sophistication are struck from your eyes and you see in the circus a gathering of men and women who are able to do things as a matter of course which you couldn’t do if your life depended on it.”
—Robert Benchley (1889–1945)