Binary search is a recursive algorithm. The high level approach is that we examine the middle element of the list. The value of the middle element determines whether to terminate the algorithm (found the key), recursively search the left half of the list, or recursively search the right half of the list.

Does binary search recursion?

Binary search is a search algorithm that finds the position of a key or target value within a array. … Like all divide and conquer Algorithms Binary Search first divide the large array into smaller sub-arrays and then solve Recursively(or iteratively).

What is recursion formula of binary search?

Recurrence relation is T(n) = T(n/2) + 1, where T(n) is the time required for binary search in an array of size n. T(n) = T( n 2k )+1+ ··· + 1 Page 2 Since T(1) = 1, when n = 2k, T(n) = T(1) + k = 1 + log2(n). log2(n) ≤ 1 + log2(n) ≤ 2 log2(n) ,∀ n ≥ 2. T(n) = Θ(log2(n)).