LiveCodingInterview.com
← Articles

How to Implement Binary Search in Java

Java remains a top language for FAANG-style interviews. Binary search on sorted arrays is a must-know pattern — and Java's integer overflow rules make midpoint calculation especially worth getting right.

Read the language-agnostic explanation first: Binary Search Algorithm: A Coding Interview Guide.

Prerequisites

  • Input array sorted ascending
  • **O(log n)** time per search, **O(1)** space (iterative)

Iterative implementation

public static int binarySearch(int[] arr, int x) {
    int lo = 0;
    int hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}

**Critical in Java:** never write `int mid = (lo + hi) / 2` on large arrays — `lo + hi` can overflow. Always use `lo + (hi - lo) / 2`.

Recursive implementation

public static int binarySearchRecursive(int[] arr, int x, int lo, int hi) {
    if (lo > hi) return -1;

    int mid = lo + (hi - lo) / 2;

    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearchRecursive(arr, x, lo, mid - 1);
    return binarySearchRecursive(arr, x, mid + 1, hi);
}

// Call: binarySearchRecursive(arr, x, 0, arr.length - 1);

Recursive depth is O(log n) — safe for arrays up to millions of elements.

Arrays.binarySearch

Java provides a built-in binary search:

import java.util.Arrays;

int[] arr = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(arr, 5); // returns 2 if found

// If not found, returns -(insertionPoint) - 1
int missing = Arrays.binarySearch(arr, 4); // negative index

Decode negative results: `insertionPoint = -(result + 1)`. In interviews, implement manually unless told otherwise.

Lower bound (first index >= x)

public static int lowerBound(int[] arr, int x) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Use this for "first occurrence" and sorted insertion point problems.

Java interview tips

  • Use `int[]` unless the problem requires objects — autoboxing adds noise
  • Guard empty input: `if (arr.length == 0) return -1;`
  • For `List<Integer>`, convert to array or use indexed `get(mid)` — avoid `subList` copies
  • Mention **O(log n)** time and **O(1)** auxiliary space when done

Complexity

  • **Time:** O(log n)
  • **Space:** O(1) iterative, O(log n) recursive stack