Problem Detail: 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.
Asked By : user3029613
Answered By : Lieuwe Vinkhuijzen
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 $quadquad$__return__ comparisons+1; $quad$ else if ($target$ < a[middle]) then $quadquad$ return $texttt{binarySearch}(a, target, low, middle-1, comparisons+2)$ $quad$ else $quadquad$ 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__ $aleft[low + frac{high-low}{3}right] = target$ return $comparisons+1$; $quad$__else if__ $aleft[low+ 2frac{high-low}{3} right] = target$ return $comparisons+2$; $quad$__else if__ $target < aleft[low + frac{high-low}{3} right]$ return $quadquadtexttt{ternarySearch}(a, target, low, low + frac{high-low}{3}-1, comparisons+3)$ $quad$ else if $target < aleft[low + 2frac{high-low}{3} right]$ return $texttt{ternarySearch}(a, target,$ $quadquad low + frac{high-low}{3}+1, low + 2frac{high-low}{3}-1, comparisons+4)$ $quad$ else return $texttt{ternarySearch}(a, target, low + 2frac{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 = 8sqrt{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)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47842 Ask a Question Download Related Notes/Documents
