Binary Search in Java: Solution, Explanation & Practice

Implement binary search on sorted array

Problem summary

Write a program that implements binary search on a sorted array.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23; // Test case 1
        
        // Implement binary search
        // Print: Found at index: <index> OR Not found
    }
}

Expected output and test cases

Find 23
```
Found at index: 5
```
Find first element
```
Found at index: 0
```
Element not in array
```
Not found
```

Hints

Maintain low and high pointers
Calculate mid and compare with target
Narrow search range each iteration

Validated solution

Reveal Java solution

public class Main {
    static int binarySearch(int[] sorted, int target) {
        int low = 0, high = sorted.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (sorted[middle] == target) return middle;
            if (sorted[middle] < target) low = middle + 1;
            else high = middle - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] values = {2, 5, 8, 12, 16, 23, 38, 56};
        System.out.println("Found at index: " + binarySearch(values, 23));
    }
}

How to approach the problem

Binary search discards half of a sorted search interval after each comparison. The invariant is that any target still possible lies between low and high inclusive.

Approach

Require ascending sorted input.
Use an overflow-safe middle expression.
Shrink the interval past middle so the loop makes progress.

Time and space complexity

Time: O(log n). Space: O(1).

Edge cases to test

An empty input returns -1.
Duplicates may return any matching index unless a first/last rule is added.

Common mistakes

Using this algorithm on unsorted values.
Changing low or high to middle instead of middle plus or minus one.

Follow-up challenge

Find the first occurrence of a duplicated target with a boundary-biased search.

Related Arrays exercises

Practice all Arrays exercises · Run this idea in the Java compiler