12

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?

1
  • 1
    cuz then it wouldn't be a BINARY search. Any more obvious questions I can answer for ya? :) Feb 26, 2010 at 0:45

11 Answers 11

18

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.

5
  • 2
    This is the right answer — it's not just that binary search is easiest, as other answers indicate, but that (when it is applicable) it is theoretically the best possible search algorithm. Feb 26, 2010 at 1:01
  • when it(hashing) is applicable hashing would probably be better. Feb 26, 2010 at 1:49
  • @ShreevatsaR: Do you have a link to a proof of binary search being the best possible search algorithm?
    – Aryabhatta
    Feb 26, 2010 at 2:05
  • Yeah sorry, that was vague without defining the problem. Suppose you have a sorted array a of size n, and want to find whether (and if yes where) a certain element s is present. The operation allowed is to pick an i and compare a[i] with s. Now, consider the worst case where s is not present, so each comparison has only 2 possible results. So with k operations, you can have only 2^k possible outputs, so you need 2^k≥n, i.e. k≥⌈log_2(n)⌉, which binary search achieves. This doesn't prove that binary search is best in all situations (not true), but it's better than any n-ary search. Feb 26, 2010 at 5:19
  • It should also be mentioned that it is the best because of how our classical computers function. In one step we do the comparison and then with the next step we choose which partition to look in based on that comparison. However, if we have a computer that can do multiple comparisons in one step and choose which partition to search in next in another step, then this fantastic computer would be faster. We're not really there yet. The quantum computer algorithm to do this has already been discovered though. Feb 26, 2010 at 6:01
5

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.

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

1
  • I would change from "splitting the array in half" to partitioning the array into two parts. +1 for beating me by 1 second and referencing Wikipedia. :) Feb 26, 2010 at 0:32
1

It considerably simplifies the logic:

if(cond)
Go Left
else
Go Right

Versus a switch statement.

0
1

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

1

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.

1

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.

1

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.

1

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.

0

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

4
  • If this were the correct answer, you'd want the base to be as large as possible, so triple search would be better than binary Feb 26, 2010 at 0:59
  • Asymptotically, O(log2 n) and O(log3 n) is the same. Check out en.wikipedia.org/wiki/Logarithm#Bases about indefinite logarithm. Feb 26, 2010 at 1:01
  • I realize that; but that has nothing to do with the question Feb 26, 2010 at 1:03
  • It has everything to do with the question. The reason why ternary search is not done is because it's still logarithmic, so what's the point? Feb 26, 2010 at 1:05
-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!]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.