Write the pseudocode of the binary search algorithm and generate the recurrence relation from it
Question
Write the pseudocode of the binary search algorithm and generate the recurrence relation from it
Solution
Sure, here is the pseudocode for the binary search algorithm:
Algorithm BinarySearch(A, n, x)
Input: An array A[0..n-1] sorted in ascending order, an integer x.
Output: An index i such that A[i]=x or the special value NOT_FOUND.
low ← 0
high ← n - 1
while low ≤ high do
mid ← (low + high) / 2
if A[mid] < x then
low ← mid + 1
else if A[mid] > x then
high ← mid - 1
else
return mid
return NOT_FOUND
Now, let's generate the recurrence relation from it.
The binary search algorithm divides the problem into two equal halves with each recursive call. Therefore, the recurrence relation for the binary search algorithm can be expressed as:
T(n) = T(n/2) + c
Here, T(n) is the time taken to search in an array of size 'n', T(n/2) is the time taken to search in the sub-array (which is half the size of the original array), and 'c' is the time taken for the comparison operations.
Similar Questions
Write down the pseudocode of the factorial of n numbers and create the best-case and worst-caserecurrence relation
Program to demonstrate the use of Binary Search to search a given element in a sorted array in ascending order.
Describe the standard algorithm for finding the decimal representation of apositive binary numbera. in English.b. in a pseudocode.
What is the recurrence relation for the linear search recursive algorithm?OptionsT(n+1)+c2T(n-1)+cT(n-2)+cT(n-1)+c
What is the recurrence relation for the linear search recursive algorithm?T(n-2)+c2T(n-1)+cT(n-1)+cT(n+1)+c
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.