Binary Search in Java

Binary Search is a simple approach to search an element in array. If you are using binary search for searching element in array, then array must be sorted in ascending order. We can sort an array using sorting algorithms or by using Arrays.sort(arr) method. Binary search is faster than linear search. Binary search is also known as Half-Interval algorithm.

In binary search, we compares the given element with the middle element of array. If middle element is equal to given element then index of the middle element is returned. If given element is less than middle element, the algorithm again repeats on the sub-array to the left of the middle element and if the given element is greater than middle element, the algorithm again repeats on the sub-array to the right of the middle element.

Binary Search in Java

class BinarySearch{
	public static void binarySearch(int arr[], int start, int end, int key){
		int mid = (start + end)/2;  
		while( start <= end ){
			if ( arr[mid] < key ){
				start = mid + 1;     
			}
			else if ( arr[mid] == key ){
				System.out.println("Element "+key+" is found at index: " + mid);  
				break;  
			}
			else{
				end = mid - 1;
			}
			mid = (start + end)/2;  
                }  
		if ( start > end ){
			System.out.println("Element is not found!");  
		}  
	}  
	public static void main(String args[]){  
        int arr[] = new int[]{10,20,30,40,50};  
        int key = 40; 
        int end = arr.length-1;  
        binarySearch(arr,0,end,key);     
 }
}

Output:

Element 40 is found at index: 3

Binary Search in Java Using Recursion

class BinarySearch{
	public static int binarySearch(int arr[], int start, int end, int key){  
        if (end>=start){  
            int mid = start + (end - start)/2;  
            if (arr[mid] == key){  
            return mid;  
            }  
            if (arr[mid] > key){  
            return binarySearch(arr, start, mid-1, key);//search in left subarray  
            }
			else{  
            return binarySearch(arr, mid+1, end, key);//search in right subarray  
            }  
        }  
        return -1;  
    }  
    public static void main(String args[]){  
        int arr[] = {10,20,30,40,50};  
        int key = 50;  
        int end=arr.length-1;  
        int result = binarySearch(arr,0,end,key);  
        if (result == -1)  
            System.out.println("Element is not found!");  
        else  
            System.out.println("Element "+key+" is found at index: "+result);  
    }  
}

Output:

Element 50 is found at index: 4

Binary Search in Java Using Arrays.binarySearch()

binarySearch() is a method in Arrays class, so we need to import java.util package.

import java.util.Arrays;  
class BinarySearch{  
    public static void main(String args[]){  
        int arr[] = {10,20,30,40,50};  
        int key = 20;  
        int result = Arrays.binarySearch(arr,key);  
        if (result < 0)  
            System.out.println("Element "+key+" not found!");  
        else  
            System.out.println("Element "+key+" is found at index: "+result);  
    }  
}

Output:

Element 20 is found at index: 1