Java Binary Search (Recursive and Iterative) Program



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

Comments