one question about binary search

Why people usually do binary 开发者_StackOverflow中文版search instead of triple search (divide the array into three parts each time) or even divide into ten parts each time?

Because binary search results in the smallest amount of comparisons and lookups. For a simple intuition consider dividing into 4 parts each time.

[         |         |    .    |         ]
          v1        v2        v3

You now have done 3 lookups and have to compare the value you are searching for at worst against all three values. Compare this with two iterations of binary search:

[                   |    .              ]
                    v1
[                   |    .    |         ]
                    v1        v2

You have now narrowed the search range by the same amount, but have done only 2 lookups and 2 comparisons.

Its because 1 comparison per level (as in binary search) has the least number of comparison in the worst case of any n-ary search. This is because the number of comparisons per level increases linearly where the depth of the tree decreases logarithmically. For n-nary search the worst case number of comparisons is ((n-1)/log(n)) *log(m) where m is the number of items in the tree, which is minimized at n=2.

Splitting an array in half requires only ONE comparison operator.

Splitting it into three would require more than one (sometimes one, sometimes two) comparison.

Wikipedia should give you a bit more explanation including the maths behind it

Binary allows for an easy comparison <= or >= or < or > (cannot remember what is typically used). It cleanly partitions the set and it is easy to come up with divisions. For arbitrary data sets, how would you divide into the different parts? How would you decide which part to put something in? Binary search takes O(log n) lookups to find. Adding more components would change that to something closer to O(m * log n) where m is the number of parts you are dividing into.

Jacob

It considerably simplifies the logic:

if(cond)
Go Left
else
Go Right

Versus a switch statement.

because binary search is based on splitting over a simple operation, division which always give one answer which means one cut point, so if you can come up with a question that has two answers you can have two cut points an so on

Primarily because it is hard to decide how to reduce the range - how to interpolate. The comparison function gives a three-way answer - less than, equal to, greater than. But typically, the comparison doesn't give 'a lot greater than' or 'a lot smaller than' as an answer. Indeed, the comparator would have to look at three values - the current test point, the searched for value, and either the 'high end of the range' or the 'low end of the range' to estimate a proportional distance.

The binary search, therefore, is simpler because it makes fewer requirements on the comparison.

No one's really mentioned that the comparison-operators implemented in all computers only compare two things at a time - if the computer could compare three objects at once, this would certainly make sense.

As it stands, to compare three values takes (at least) two operations.

Actually, N-way search trees rather than binary trees are typically used in database systems. While the number of comparisons may be larger than O(log2 n), the number of read operations is substantially less. Check out B-trees and their variants.

The reasoning is because you don't actually gain anything from it: the search is still O(log n), just with a different base.

Binary search uses 1 comparison to cut n to n/2. ternary search uses 2 comparisons to cut n to n/3.

So complexity of former is 1. log2 n, that of latter 2. log3 n or log3 n^2

log2 n is always better than log3 n^2.

To see this,

raising both to the power of 3, 3^log2 n vs n^2

=> 3^ (log2 3 . log3 n) vs n^2

=> n^ (log2 3) vs n^2

so binary search is faster over any m-ary search. you are comparing log2 m vs (m-1) .

As an aside, interpolation search is asymptotically faster than binary search with loglogN. But it is not worthing going to the the trouble, unless your data is huge. [so the comment above about best possible search theoretically is wrong!]