LiveCodingInterview.com
← Articles

How to Implement Binary Search in Java

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

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

What Do You Need Before Binary Search Works in Java?

  • The input array must be sorted in ascending order
  • Time complexity is O(log n) per search, with O(1) space for the iterative version

How Do You Write the 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;
}

Never write int mid = (lo + hi) / 2 on large arrays, since lo + hi can overflow a 32-bit int well before either index gets close to Integer.MAX_VALUE. Always use lo + (hi - lo) / 2 instead, and say so out loud if an interviewer asks why it matters.

How Do You Write the 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), which stays safe for arrays up to millions of elements without any real risk of a stack overflow.

java.util.Arrays provides a built-in binary search for arrays:

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 a negative result with insertionPoint = -(result + 1). java.util.Collections offers the same method for a sorted List, Collections.binarySearch(list, key), which is the version to reach for when your input is a List<Integer> instead of a raw array. In interviews, implement the loop by hand unless the interviewer explicitly says library calls are fine.

How Do You Write a Lower Bound Helper?

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 template for first-occurrence and sorted-insertion-point problems, the same pattern the main binary search guide covers in more depth.

What Should You Watch for in a Java Interview?

Use a primitive int array instead of Integer objects when the problem allows it, since autoboxing adds overhead and noise that has nothing to do with the algorithm. Guard against empty input explicitly: if arr.length == 0, return -1 before the loop ever runs. When you are handed a List<Integer> instead of an array, convert it to an array first or index into it with get(mid) directly, and avoid subList, which copies the underlying data and quietly changes your space complexity. State both O(log n) time and O(1) auxiliary space once you finish, the same way you would for any other language.

What's the Time and Space Complexity?

Both versions run in O(log n) time. The iterative version uses O(1) space, while the recursive version uses O(log n) space on the call stack, since each call frame stays alive until its base case returns.

How Do You Search a Sorted 2D Matrix in Java?

Interviewers often hand you a matrix where every row is sorted left to right and the first value in each row is larger than the last value in the row before it, which makes the whole grid behave like one long sorted array with no extra structure to exploit. Treat the matrix as flattened without ever copying it into a real array: index i in that flattened view maps to row i / cols and column i % cols, so the same loop from the plain array version still works once mid gets translated into those two coordinates.

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int lo = 0;
    int hi = rows * cols - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int value = matrix[mid / cols][mid % cols];

        if (value == target) return true;
        if (value > target) hi = mid - 1;
        else lo = mid + 1;
    }

    return false;
}

This still runs in O(log(rows times cols)) time and O(1) space, and it skips the more common approach of running two separate searches, one to pick the row and one inside it. That two-search version also works, but it adds code an interviewer has to read through for no real benefit once you know the flattening trick.

How Do You Write a Generic Binary Search With a Comparator?

Real interview code sometimes hands you an array of custom objects instead of primitive ints, and Java's Arrays.binarySearch only accepts elements that implement Comparable or an explicit Comparator, so having your own generic version ready is worth the five minutes it takes to write.

public static <T> int binarySearch(T[] arr, T target, Comparator<T> cmp) {
    int lo = 0;
    int hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int result = cmp.compare(arr[mid], target);

        if (result == 0) return mid;
        if (result > 0) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}

Pass Comparator.naturalOrder() when T already implements Comparable, or a lambda such as (a, b) -> a.getPrice() - b.getPrice() when you need to search on a single field of a larger object. The loop body never changes here. Only the comparison call does, and that detail is what tells an interviewer you understand binary search as a comparison-based algorithm rather than something that only works on raw numbers.

What Is Binary Search on the Answer, and When Do You Need It?

Some of the hardest binary search questions never mention searching an array at all. Instead they ask for the smallest or largest value that satisfies some condition, such as the minimum number of days needed to ship a set of packages under a weight limit, or the smallest boat capacity that still moves every load across a river within a limit on trips. The trick is noticing that the range of possible answers is sorted in a specific sense: if a given capacity works, every larger capacity also works, and if a capacity fails, every smaller one fails too. That monotonic property is exactly what binary search needs, even though nothing about the problem resembles searching a sorted array.

public static int minCapacity(int[] weights, int days) {
    int lo = Arrays.stream(weights).max().getAsInt();
    int hi = Arrays.stream(weights).sum();

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canShipWithinDays(weights, mid, days)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}

canShipWithinDays is a helper that greedily packs weights into as few days as possible for a given capacity and checks whether that count still fits inside the limit. Binary search here searches the space of possible capacities, not an array of weights, and writing that predicate function correctly is almost always the harder half of the problem. Say that framing out loud as soon as you notice it, since naming the pattern signals you recognize it rather than treating every new parametric search problem as an unfamiliar shape.

What Mistakes Break a Java Binary Search in an Interview?

A handful of mistakes show up again and again in Java binary search interviews specifically. Comparing boxed Integer objects with == instead of .equals or a direct value comparison breaks silently for values outside the range negative 128 to 127, since Java only caches and reuses Integer objects inside that range, so two equal values above it can be different objects that == reports as unequal. Updating the wrong bound, setting lo = mid instead of lo = mid + 1 inside a lower-bound search, is the single most common source of an infinite loop, since the search space never shrinks once mid already equals lo. Skipping the empty-array guard throws an ArrayIndexOutOfBoundsException the moment arr.length - 1 goes negative before the loop ever starts. And calling Collections.binarySearch on a List that was never actually sorted returns a meaningless result instead of an error, since the method has no way to detect that its own precondition was violated.

Frequently Asked Questions

Does Arrays.binarySearch work correctly on an unsorted array?

No, and it will not throw an error to warn you either. The method assumes the input is already sorted and returns whatever index its internal comparisons happen to land on, which is meaningless if that assumption is false. Sort the array first, or use a different search entirely if sorting is not an option.

Why use lo + (hi - lo) / 2 instead of (lo + hi) / 2 in Java?

Because lo + hi can overflow a 32-bit int on large arrays well before either index gets close to Integer.MAX_VALUE, and an overflowed sum wraps around to a negative number that produces a nonsensical midpoint. lo + (hi - lo) / 2 reaches the same value without ever letting the intermediate sum exceed either bound.

Can you binary search a LinkedList in Java?

Technically yes through Collections.binarySearch, but it defeats the point. A LinkedList has no random access, so reaching the middle element takes O(n) time on every single comparison, which turns an algorithm that should run in O(log n) into something closer to O(n log n) overall. Convert to an array or use an ArrayList if you need repeated binary searches on the same data.

What is binary search on the answer, in one sentence?

It is binary searching over the space of possible answers instead of over an array, using a predicate function that returns true or false for a candidate answer, applicable whenever that predicate is monotonic across the range of possible values.

Is Collections.binarySearch different from Arrays.binarySearch?

They behave the same way and return the same kind of result, a nonnegative index if found or a negative insertion-point encoding if not, but Arrays.binarySearch works on a raw array while Collections.binarySearch works on a List, most commonly an ArrayList where random access stays fast.