1
$\begingroup$

I have a piece of code that applies recursive Binary and Ternary searches on sorted arrays of increasing size, i.e. 500, 1000, 2000, 4000, etc. The entire code segment is about 200 lines so I've been forced to upload it to Pastebin which you can find here. When the main method is executed, arrays are created and populated according to some heuristic, which here happens to be A[i] = 8 * sqrt(i). The arrays are then searched to see if they contain a key that's randomly generated and may or may not be in the array.

I've ran the tests over a dozen times and each time, the ternary search outperforms the binary search in terms of average comparisons needed before finding the key or knowing that it's not in the array. Shouldn't Binary Search have fewer comparisons if it's a better complexity (log(2) (n) instead of 2*log(3)(n))? Are my sample sizes too small or have I made a mistake in my code somewhere? For example, here's some sample output:

Binary search results:

Average number of comparisons for array of size 500: 7.4
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 8.1
Average number of comparisons for array of size 4000: 9.3
Average number of comparisons for array of size 8000: 9.0

Ternary search results:

Average number of comparisons for array of size 500: 4.6
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 5.3
Average number of comparisons for array of size 4000: 5.9
Average number of comparisons for array of size 8000: 6.0

Note: The 'y' variable in the code is the number of comparisons, this is an assignment and that's what it's supposed to be named as per the specs.

$\endgroup$
5
  • 6
    $\begingroup$ The 'y' variable in the code doesn't really measure the number of comparisons, but only the depth in the search tree. So your results are not really that surprising. $\endgroup$ Oct 4, 2015 at 5:38
  • $\begingroup$ I didn't look at the code, but measure also the time to find an element. Also, (and this is general advice), make sure your inputs are large enough. Think about the structure your input has as well. $\endgroup$
    – Juho
    Oct 4, 2015 at 7:31
  • $\begingroup$ @ThomasKlimpel Make that an answer? $\endgroup$
    – Raphael
    Oct 4, 2015 at 9:03
  • $\begingroup$ This experiment is ... flawed.. It uses a very specific set of inputs, so you don't measure worst-, best-, or (uniform) average-case. How do you know these instances are not a bad case for one but not the other algorithm? Note also that the numbers you quote -- $\log_2 n$ vs $2 \log_3 n$ -- are the respective worst-case figures. So they don't imply anything about the result of a randomized experiment. $\endgroup$
    – Raphael
    Oct 4, 2015 at 9:06
  • $\begingroup$ The results look a bit weird as well. When you see that binary search in an array of size 500 takes longer than size 1,000 and size 4,000 takes longer than size 8,000 your reaction should be "WTF is going on here". $\endgroup$
    – gnasher729
    Dec 14, 2016 at 11:49

1 Answer 1

2
$\begingroup$

As already noted in the comments, the experiment doesn't measure the amount of comparison operations, but instead it measures the depth of the recursion needed to find the given number. Here's code that should produce a proper experiment (replacing value $\rightarrow target$, lo $\rightarrow low$, $hi \rightarrow high$, $y \rightarrow comparisons$ for readability):

int $\texttt{binarySearch}$(array $a$, int $target$, int $low$, int $high$, int $comparisons$):

$\quad$__int__ middle = $\frac{low+high}{2}$;

$\quad$ if ($a$[middle] $= target$) then

$\quad\quad$__return__ comparisons+1;

$\quad$ else if ($target$ < a[middle]) then

$\quad\quad$ return $\texttt{binarySearch}(a, target, low, middle-1, comparisons+2)$

$\quad$ else

$\quad\quad$ return $\texttt{binarySearch}(a, target, middle+1, high, comparisons+2)$;

And similarly for $\texttt{ternarySearch}$:

int $\texttt{ternarySearch}($array $a$, int $target$, int $low$, int $high$, int $comparisons$):

$\quad$__if__ $a\left[low + \frac{high-low}{3}\right] = target$ return $comparisons+1$;

$\quad$__else if__ $a\left[low+ 2\frac{high-low}{3} \right] = target$ return $comparisons+2$;

$\quad$__else if__ $target < a\left[low + \frac{high-low}{3} \right]$ return

$\quad\quad\texttt{ternarySearch}(a, target, low, low + \frac{high-low}{3}-1, comparisons+3)$

$\quad$ else if $target < a\left[low + 2\frac{high-low}{3} \right]$ return $\texttt{ternarySearch}(a, target,$

$\quad\quad low + \frac{high-low}{3}+1, low + 2\frac{high-low}{3}-1, comparisons+4)$

$\quad$ else return $\texttt{ternarySearch}(a, target, low + 2\frac{high-low}{3}, high, comparisons+4)$

Hope this helps. You might still have to catch the $low > high$ case. Lastly, you test your cases by populating your array with $a_i = \sqrt{i}$, and then measuring with $\texttt{xSearch}(rand(max = 8\sqrt{n}))$. Is there any reason you test specifically that way? Your results will be skewed because you will (especially with larger $n$) query your array for relatively low indices. It is better methodologically, unless your target application is representative of this test case, to populate your list with numbers $1 \ldots n$, and then to shuffle the list at random, to produce a random permutation. Then query for item $rand(max=n)$.

$\endgroup$
5
  • $\begingroup$ I appreciate the help - your system of returning an incrementing number of comparisons with each block is a great solution. As for the strange way the array is populated and then searched, I have no control over that, this is part of an assignment for a class and those are the specs I have to use. $\endgroup$ Oct 4, 2015 at 22:46
  • $\begingroup$ Glad to help. Be advised that the largest index queried is $8\sqrt{n}$, so #178 in the case of an array of 500 length, and #609 for ar8000. It may be worthwhile to ask a TA why that's the case. $\endgroup$ Oct 4, 2015 at 23:13
  • $\begingroup$ I updated my code accordingly and re-ran the tests and now I'm getting Stack Overflows at random points of execution - sometimes it finishes all of the binary tests and overflows at the ternary tests, sometimes (such as here) it doesn't even make it through many of the small binary tests: Binary search results: Average number of comparisons for array of size 500: 11.2 Exception in thread "main" java.lang.StackOverflowError at Search.binSearch(Search.java:52) However, it's always overflowing at the same point: the last else case (for either bin/ternary). Any idea why this is the case? $\endgroup$ Oct 4, 2015 at 23:16
  • $\begingroup$ That shouldn't happen. I didn't pay much attention to rounding the numbers, maybe that's it though looking at my code it doesn't seem too bad. Did you keep the $low > high$ then return error safeguards? and if $low = high$ then return $comparisons$? Can you post your new code to pastebin the way to you did the last? $\endgroup$ Oct 4, 2015 at 23:19
  • $\begingroup$ Sure, here it is - pastebin.com/p40bbynY. I did add lo>hi tests at the beginning of each, as well as two additional tests to check if a[lo] or a[hi] was the key being searched for. Here's a picture of most recent test using the exact same code in the Pastebin - gyazo.com/4ae2f88aada93bcb71f2bccd40c1ab43. For reference, line 30 is the final else block in the ternary search: else { return ternarySearch(a, key, lo+(2*(hi-lo)/3), hi, comparisons+4); $\endgroup$ Oct 4, 2015 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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