Java Binary Search

Introduction

Binary Search is an efficient search algorithm used to find a value in a sorted array. It is faster than linear search because it eliminates one-half of the array after each iteration. In this lab, we will learn the steps to implement the binary search algorithm in Java.

Skills Graph

Create a Sorted Array

The binary search algorithm requires a sorted array, so we will first create a sorted array.

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

Implement Binary Search Iteratively

We will now implement the binary search algorithm iteratively. This method returns the index of the element if it is present in the array. Otherwise, it returns -1.

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

To run the code, we first need to call the binarySearchIterative method, pass sortedArray and the element we want to search as parameters.

## compile java file
javac BinarySearch.java

## run the file
java BinarySearch

Implement Binary Search Recursively

We will now implement the binary search algorithm recursively. This method also returns the index of the element if it is present in the array. Otherwise, it returns -1.

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

To run the code, we need to call the binarySearchRecursive method, pass sortedArray, the element we want to search, leftIdx, and rightIdx as parameters.

Use Inbuilt Methods for Binary Search

We also have inbuilt functions in Java to implement binary search. These functions are Arrays.binarySearch() and Collections.binarySearch(). We can use these functions to search an element in a sorted array.

The Arrays.binarySearch() function takes a sorted array and a key value to search as parameters. The function returns the index of the key if it is present in the array. Otherwise, it returns -1.

int index = Arrays.binarySearch(sortedArray, 6);

The Collections.binarySearch() function can be used on collections like ArrayLists to search for an element. The function takes the sorted collection and a key as parameters and returns the index at which the key is present. Otherwise, it returns -1.

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

Test

We will now test all the methods and print the output.

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}

To run the code, we first compile the java program.

javac BinarySearch.java

Then we can run the program.

java BinarySearch

Summary

This lab covered the steps required to implement the binary search algorithm iteratively and recursively in the Java programming language. We also learned about the inbuilt methods Arrays.binarySearch() and Collections.binarySearch() to implement binary search. We created a sorted array and used different methods to search for elements in it.