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

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

Answer 2

It considerably simplifies the logic:

if(cond)
Go Left
else
Go Right

Versus a switch statement.

Answer 3

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.

Answer 4

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

Answer 5

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.