Binary Search in Java

Binary search is a searching techniques which is used when the array is sorted. In Binary Search the middle element that acts as a reference key which is used to decide whether to go left or right of the sorting list. This searching helps in optimizing the search technique with every iteration is referred to as binary search.Binary search is faster than linear search.

Binary Search Algorithm in Java

1) Start
2) Take input array and Target
3) Initialise start = 0 and end = (array size -1)
4) Intialise mid variable
5) mid = (start+end)/2
6) if array[ mid ] == target then return mid
7) if array[ mid ] < target then start = mid+1 8) if array[ mid ] > target then end = mid-1
9) if start<=end then goto step 5
10) return -1 as Not element found
11) Exit

Methods for Java Binary Search

There are three methods in Java to implement Binary Search in Java are mentioned below:

1) Iterative Method
2) Recursive Method
3) Inbuild Method

Program 1 : Binary Search Example in Java using Iterative Method (Iterative Method)

public class BinarySearchIterative {

	public static int binarySearch(int a[], int leftSide, int rightSide, int keyElement)
    {
        while (leftSide <= rightSide) {
            int middleElement = (leftSide + rightSide) / 2;

            if (a[middleElement] == keyElement) {
                return middleElement;

            } else if (a[middleElement] > keyElement) {
            	rightSide = middleElement - 1;
            } else {
            	leftSide = middleElement + 1;
            }  
        }

        // No Element Found
        return -1;
    }
		 
	public static void main(String args[]){  
    		int arr[] = { 20, 23, 38, 48, 51,78}; // Array Index Start From zero
	        int arrSize = arr.length;
	        int key = 51;
	      
	        int res = binarySearch(arr, 0, arrSize - 1, key);

	        if (res == -1)
	            System.out.println("Element not present");
	        else
	            System.out.println("Element found at index " + res);

		 }
}

Output:

Element found at index 4

Program 2 : Binary Search Example in Java using Recursion (Recursive Method)

public class BinarySearchRecursive {

	public static int binarySearch(int arr[], int firstElement, int lastElemet, int key){  
		
        if (lastElemet>=firstElement){  
            
        	int midElement = firstElement + (lastElemet - firstElement)/2;  
           
            if (arr[midElement] == key){  
            	return midElement;  
            }  
            
            if (arr[midElement] > key){  
            	return binarySearch(arr, firstElement, midElement-1, key);//search in left subarray  
            }
            else{  
            	return binarySearch(arr, midElement+1, lastElemet, key);//search in right subarray  
            }  
        }  
        
        return -1;  
    }  
    public static void main(String args[]){  
		   
    	int arr[] = { 20, 23, 38, 48, 51,78}; // Array Index Start From zero
        int key = 48;  
        int last=arr.length-1;  
        int result = binarySearch(arr,0,last,key);  
        if (result == -1)  
            System.out.println("Element is not found!");  
        else  
            System.out.println("Element is found at index: "+result);  
    }
}

Output:

Element is found at index: 3

Program 3 : Binary Search Example in Java using Arrays.binarySearch() (Inbuild Method)

import java.util.Arrays;

public class BinarySearchInbuilt {

	public static void main(String args[]){  
		   
    	int arr[] = { 20, 23, 38, 48, 51,78}; // Array Index Start From zero
        int key = 78;  
        int result = Arrays.binarySearch(arr,key);  
        if (result < 0)  
            System.out.println("Element is not found!");  
        else  
            System.out.println("Element is found at index: "+result);  
    }  
}

Output:

Element is found at index: 5

Program 4 : Binary Search in Java Collections

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchCollection {

	public static void main(String[] args) { 
        List<Integer> list = new ArrayList<>(); 
        list.add(29); 
        list.add(38); 
        list.add(59); 
        list.add(76); 
        list.add(83); 
  
       
        Collections.sort(list);  
  
        int target = 30;  
        int index = Collections.binarySearch(list, target);  
  
        if (index >= 0) {  
            System.out.println("Element found at index: " + index);  
        } else {  
            System.out.println("Element not found ");  
        }  
        
        
         target = 76;  
         index = Collections.binarySearch(list, target);  
  
        if (index >= 0) {  
            System.out.println("Element found at index: " + index);  
        } else {  
            System.out.println("Element not found ");  
        }  
    }  

}

Output:

Element not found 
Element found at index: 3