Pad 10:05 PM HW1.pdf Searching & Sorting We talked about how binary search compa
ID: 3786857 • Letter: P
Question
Pad 10:05 PM HW1.pdf Searching & Sorting We talked about how binary search compares a number to be searched with the middle element of a sorted array, successively searching the right half of the array if the number is greater than the CS 201 Homework 1 Due February 3 middle element or the left half of the array if the number is less than the middle element. This is performed until the number has been found or (in the worst case) until the half of the array to be searched contains no elements (at which point we conclude that the number is not in the array) We also discussed how this algorithm is O(log2 n) because as the array size (n) doubles, the number of comparisons needed increases by 1. Now consider ternary search, which compares a number to be searched with the elements that are a third of the way from the ends of a sorted array. Essentially, this algorithm breaks the sorted array into three parts and chooses to continue searching in the one that the number to be searched would have to fall into. For example, suppose we have the sorted array array 1, 4, 6, 9, 10, 11, 14, 20, 25, 33, 38 and we are looking for the number 15. The "breakpoints" of the array are at array C3], which is 9, and array C7], which is 20. Since 15 is between 9 and 20, we look at the middle third of the array, which contains 10, 11, and 14. Again, we continue searching just one third of each successive array until we find the number or reach an array with no elements.Explanation / Answer
1. The worst case time complexity is O(log3 n).
Only the base of logarithm differs . In binary search its O(log2 n). Where as in ternary search its O(log3 n).
This is obtained using T(N) = T(2N/3) + 1
Solving this recurrance we get T(N) = O(log3 n). = > O(log n)
2. Coming to comparisoon on data between binary search and ternary search.
Ternary search performs three way comparison to two way comparison in binary search. Thus three way comparison is more expensive than two way comparsion.
Coming to the analysis :-
We know that the Total number of comparison made by d-way search is (d - 1) logd n.
1. For binary search d = 2, so Its (2-1) log2n = log2n.
2 . For Ternary search d = 3, so Its (3-1) log3n = 2log3n.
Thus the number of comparison made by ternary search is more than binary search hence binary search is better.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.