Binary Search Algorithm implementation in Java

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 for the first half otherwise apply the same process to the second half. 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)  , this is because we are always considering one half of the input list throwing out the other half. To solve this Recurrence relation if we use Divide and Conquer Master theorem, we get, T(n)=O(logn)

Time complexity : O(logn)   :: Space complexity : O(1) [for iterative algorithm]

Binary Search Algorithm implementation in Java

Here is the implementation for binary search iterative implementation in Java

Leave a Comment