Reputation: 25868

one question about binary search

Why people usually do binary search instead of triple search (divide the array into three parts each time) or even divide into ten parts each time?

Upvotes: 12

Answers (10)

TheJacobTaylor

Reputation: 4143

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.

Upvotes: 1

xpda

Reputation: 15813

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.

Upvotes: 1

Bishnu

Reputation: 873

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.

Upvotes: 5

BlueRaja - Danny Pflughoeft

Reputation: 85966

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.

Upvotes: 1

polygenelubricants

Reputation: 383726

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

Upvotes: 0

Ants Aasma

Reputation: 54882

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.

Upvotes: 18

Jonathan Leffler

Reputation: 753615

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.

Upvotes: 1

bashmohandes

Reputation: 2376

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

Upvotes: 1