Binary Search In Java

Binary search is used to search an key element from array of elements. Binary search is faster than linear search. It can be used when the elements are in a sorted sequence and all the key elements are unique. It takes O(logn) time where as the linear search takes O(n) time in worst case.

Algorithm:

• Compare the middle element with key

• If the middle element matches with the key, then return index of middle element

• Else if middle elements is greater than key, then key can only be lie on half sub array before the mid so we recursively find the key in half sub array

• Else key can be found in half sub array after the mid

Code:

Import library

import java.util.*;

Create a class called BinarySearch

class BinarySearch
{
}

Add methods searchHelper and search.

public static int searchHelper(int[] arr,int low,int high,int key)
	{

		if(low<=high) {

			int mid = (low+high)/2;

			if(arr[mid] == key) {
				return mid;
			}
			else if(arr[mid]>key) {
				return searchHelper(arr,low,mid-1,key);
			}
			else {
				return searchHelper(arr,mid+1,high,key);
			}
		}

		// if key is not found
		return -1;
	}


	public static void search(int[] arr,int key)
	{

		int value = searchHelper(arr,0,arr.length-1,key);
		System.out.println("The key "+key+ " is found at index "+value);
	}

searchHelper method is used to search the key element from an array recursively.

Main method:

public static void main(String[] args)
	{
		int[] arr = new int[]{3,5,7,8,9,1,15,13,78,4,34,89,23,12};
		Arrays.sort(arr);
		search(arr,7);
		search(arr,13);
		search(arr,89);
		search(arr,12);
	}

Output: