In: Computer Science
Consider the recursive formulation of the Binary Search algorithm. Given a sorted and non-decreasing list of comparable objects L, and a new item x, find the location (index) of x or indicated that x is not in L.
5a) Give a recursive algorithm for binary search. No, while, for, repeat etc statements are allowed. Only if, if else and assignment statements are allowed.
5b) Write a difference equation for the running time of your Binary Search algorithm. Solve your equation and express the performance of the algorithm in Θ(·) notation.
SOLUTION:
BINARY SEARCH :
Search a sorted array by repeatedly dividing the search interval in half.
Begin with an interval covering the whole array.
Consider array to be sorted in non-decreasing order (i.e. ascending order as mentioned in the question)
If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half of the array. Otherwise narrow it to the upper half.
Repeatedly check until the value is found or the interval is empty.
The logic is to keep ignoring a half of the search array after every comparison
Algorithm Explanation (recursion algorithm):
List of array = L
New item to be searched = x
Algorithm:
BS (L, lower, upper)
{
if ( lower < upper)
{
mid = (lower + upper) / 2;
if ( x = = L[mid] )
return mid;
else if ( x < L[mid] )
return BS (L, lower, mid-1)
else
BS (L, mid+1, upper)
}
Print (“x Not Found”);
}
Time Complexity:
The time complexity of Binary Search can be written as (the array is getting divided into half of itself with every check):
T(n) = T(n/2) + c ;where, T(1) = 1
**********************************************************
Please comment for any further help on this question.