Binary Search in Java

by

Binary search is an optimized algorithm to perform searching operation. It follows Divide and Conquer approach for searching.

Pre-condition of Binary search :

To perform Binary search the array should be sorted in ascending or descending order.

Logic of Binary Search

Let us consider array is sorted in ascending order.

Now we compare the element to be searched with the middle element of array. If the element is greater than the middle element then we perform the search in right half of the middle element. If the element is lesser then we perform the search in left half of the middle element.

Now let us consider element was smaller than middle element so we went to left half. Now we will find middle element in left half of the array and compare our element with middle element of left half. Again if the element is smaller than middle element of left half we search in left half otherwise right half.

This process goes on until element is found.

Let us see the code of Binary Search now :

public class Tech4Humans {

	static int BinarySearch(int[] arr, int elem) {
		int last = arr.length-1;
		int first = 0;
		int indexOfElement = -1;
		do 
		{
			int middle = (first+last)/2;
			if(elem > arr[middle]) 
			{
				first = middle+1;
			}
			else if(elem < arr[middle]) 
			{
				last = middle-1;
			}
			else if(elem == arr[middle]) 
			{
				indexOfElement=middle;
				break;
			}
		}while(last>=first);
		
		return indexOfElement;
	}
	
	
	public static void main(String[] args) 
	{
		int arr[] = {2, 17, 28, 30, 45, 54, 60, 78, 80 ,94};
		
		int indexOfElement = BinarySearch(arr, 54);
		
		if (indexOfElement == -1) 
		{
			System.out.println("Element not found");
		} 
		else 
		{
			System.out.println("Element found at index : " + indexOfElement);
		}
	}
}

Ouput

Element found at index : 5

Complexity of Binary Search

Linear search algorithm perform search in O(n) complexity whereas Binary Search perform search in O(log n) complexity where n is number of element in array.

Leave a Comment