In this post, we will discuss different ways to implement the Binary Search algorithm in Java.

Binary Search algorithm compares the key value with the middle element of the array; if they are unequal, the half in which the key cannot be part of is eliminated, and the search continues for the remaining half until it succeeds.

Remember – the key aspect here is that the array is already sorted.

Java Binary Search (Recursive and Iterative) Program

In this following program, we implement Binary Search in four ways:

1. Binary Search Iteratively
2. Binary Search Recursively
3. Binary Search using Java Arrays
4. Binary Search usingJava Collections

package net.sourcecodeexamples.java.search;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BinarySearch {

    public int runBinarySearchIteratively(int[] sortedArray, int key, int low, int high) {

        int index = Integer.MAX_VALUE;

        while (low <= high) {

            int mid = (low + high) / 2;

            if (sortedArray[mid] < key) {
                low = mid + 1;
            } else if (sortedArray[mid] > key) {
                high = mid - 1;
            } else if (sortedArray[mid] == key) {
                index = mid;
                break;
            }
        }
        return index;
    }

    public int runBinarySearchRecursively(int[] sortedArray, int key, int low, int high) {

        int middle = (low + high) / 2;
        if (high < low) {
            return -1;
        }

        if (key == sortedArray[middle]) {
            return middle;
        } else if (key < sortedArray[middle]) {
            return runBinarySearchRecursively(sortedArray, key, low, middle - 1);
        } else {
            return runBinarySearchRecursively(sortedArray, key, middle + 1, high);
        }
    }

    public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) {
        int index = Arrays.binarySearch(sortedArray, key);
        return index;
    }

    public int runBinarySearchUsingJavaCollections(List < Integer > sortedList, Integer key) {
        int index = Collections.binarySearch(sortedList, key);
        return index;
    }

    public static void main(String[] args) {

        BinarySearch binarySearch = new BinarySearch();

        int[] sortedArray = {
            0,
            1,
            2,
            3,
            4,
            5,
            5,
            6,
            7,
            8,
            9,
            9
        };
        int key = 5;
        int low = 0;
        int high = sortedArray.length - 1;
        List < Integer > sortedList = Arrays.asList(0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9);

        int result = binarySearch.runBinarySearchIteratively(sortedArray, key, low, high);
        System.out.println("runBinarySearchIteratively result -> " + result);

        result = binarySearch.runBinarySearchRecursively(sortedArray, key, low, high);
        System.out.println("runBinarySearchRecursively result -> " + result);

        result = binarySearch.runBinarySearchUsingJavaArrays(sortedArray, key);
        System.out.println("runBinarySearchUsingJavaArrays result -> " + result);

        result = binarySearch.runBinarySearchUsingJavaCollections(sortedList, key);
        System.out.println("runBinarySearchUsingJavaCollections result -> " + result);
    }
}

Output

runBinarySearchIteratively result -> 5
runBinarySearchRecursively result -> 5
runBinarySearchUsingJavaArrays result -> 5
runBinarySearchUsingJavaCollections result -> 5