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
    $\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$ – Thomas Klimpel Oct 4 '15 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 '15 at 7:31
  • $\begingroup$ @ThomasKlimpel Make that an answer? $\endgroup$ – Raphael Oct 4 '15 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 '15 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 '16 at 11:49
1
$\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$
  • $\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$ – user3029613 Oct 4 '15 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$ – Lieuwe Vinkhuijzen Oct 4 '15 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$ – user3029613 Oct 4 '15 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$ – Lieuwe Vinkhuijzen Oct 4 '15 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$ – user3029613 Oct 4 '15 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.