Given the following recursive binary search algorithm for finding an element in
ID: 3661881 • Letter: G
Question
Given the following recursive binary search algorithm for finding an element in a sorted array of integers:
int recursiveBinarySearch(int[] array, int target, int left, int right)
{
if (left > right)
return -1;
int middle = (left + right) / 2;
if (array[middle] == target)
return middle;
if (array[middle] > target)
return recursiveBinarySearch(array, target, left, middle - 1);
return recursiveBinarySearch(array, target, middle + 1, right);
}
Assume n is the length of the array. Find the initial condition and recurrence equation that expresses the execution time for the worst case of this algorithm and then solve that recurrence.
Explanation / Answer
Initial Condition:
if (left > right)
return -1;
recurrence equation that expresses the execution time for the worst case of this algorithm
recursiveBinarySearch(array, target, left, middle - 1);
return recursiveBinarySearch(array, target, middle + 1, right);
worst case time :
T(N)= T(N/2)+1
e-writing the recurrence relation for N/2, N/4, …, 2
T(N) = T(N/2) + 1
T(N/2) = T(N/4) + 1
T(N/4) = T(N/8) + 1
……
T(4) = T(2) + 1
T(2) = T(1) + 1
Next we sum up the left and the right sides of the equations above:
T(N) + T(N/2) + T(N/4) + T(N/8) + … +T(2) =
T(N/2) + T(N/4) + T(N/8) + … +T(2) + T(1) + (1 + 1 + … + 1)
The number of 1’s on the right side is LogN
Finally, we cross the equal terms on the opposite sides and simplify the remaining sum on the right side:
T(N) = T(1) + LogN
T(N) = 1 + LogN
Therefore the running time of binary search is:
T(N) = O(LogN)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.