Binary Search Algorithm in Java

In this post, we will 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 two ways:

1. Binary Search Iteratively
2. Binary Search Recursively

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 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);
    }
}

Output

runBinarySearchIteratively result -> 5
runBinarySearchRecursively result -> 5