Knowee
Questions
Features
Study Tools

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

🧐 Not the exact question you are looking for?Go ask a question

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.

This problem has been solved

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

1/1

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.