Let me explain the Binary Search algorithm through a well known example of Dictionary. Let us consider, searching a word in a dictionary, in general we directly go to some approximate page [say middle page] start searching from that point. If the name that we are searching is same, then we are done with the search. If the page is before the selected pages then apply the same process[call the method to itself with different arguments to do the process] for the first half otherwise apply the same process to the second half [call the method to itself, with second half related arguments]. Binary Search also works in similar fashion considering one half of the list and throwing the other half. Algorithm following such a strategy is called Binary Search.
Recurrence for binary search algorithm T(n)=T(n/2)+Θ(1)+Sack Overhead , this is because we are always considering one half of the input list throwing out the other half and as we are using Recursion, a function calling to it self, It uses Stack space pushing and popping of activation records of method calls.
To solve this Recurrence relation if we use Divide and Conquer Master theorem, we get, T(n)=O(logn) +Stack Overhead
Time complexity : O(logn) :: Space complexity : O(logn) [for Recursive algorithm]
As stack overhead is involved, this algorithm must be little slower than iterative approach.
Binary Search Algorithm implementation with Recursion
package com.jminded.algorithms.search;
public class BinarySearchRecursiveAlgorithm {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={0,1,2,4,5,6,7};
int searchIndex=binarySearch(arr,3,0,arr.length);
System.out.println("Element at search index "+searchIndex);
searchIndex=binarySearch(arr, 7,0,arr.length);
System.out.println("Element at search index "+searchIndex);
}
/**
* <p>Binary Search Recursive Algorithm</p>
* @param a
* @param number
* @param low
* @param high
* @return search Index
* Recurrence relation :: T(n/2)+O(1)
* Time Complexity :: O(logn)
*
*/
public static int binarySearch(int[] a,int number,int low,int high){
int mid=low+(high-low)/2;
if(low>high){
return -1;
}else{
if(a[mid]==number)
return mid;
else if(a[mid]<number) //recursive case.
return binarySearch(a, number, mid+1, high);
else
return binarySearch(a, number, low, mid-1);
}
}
}