one question about binary search

Question

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?

Answer 1

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!]

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.