Binary Search Algorithm implementation in Java

by

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

package com.jminded.algorithms.search;

public class BinarySearchIterativeAlgorithm {

	/**
	 * @author Umashankar
	 * {@link https://jminded.com}
	 * @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);
		System.out.println("Element at search index "+searchIndex);
        searchIndex=binarySearch(arr, 7);
        System.out.println("Element at search index "+searchIndex);

	}
	/**
	 * <p>Binary Search Algorithm</p>
	 * @param a
	 * @param number
	 * @return
	 * Time Complexity ::  O(logn)
	 * Space Complexity::  O(1)
	 */
	public static int binarySearch(int[] a,int number){
		int n=a.length;
		int low=0;
		int high=n-1;
		while(low<=high){
			int mid=low+(high-low)/2; //To avoid overflow
			if(a[mid]==number)
				return mid;
			else if(a[mid]<number)
				 low=mid+1;
			else
				 high=mid-1;
		}
		return -1;
	}
}

Leave a Comment