Binary Search in Java: Solution, Explanation & Practice

Find target in sorted array

Problem summary

Given a sorted array and target value, return the index of target, or -1 if not found. Implement classic binary search.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        
        // left = 0, right = n-1
        // mid = left + (right - left) / 2
        // Adjust bounds based on comparison
        // Print: Index: 4
    }
}

Expected output and test cases

9 found at index 4
```
Index: 4
```
2 not found
```
Index: -1
```
First element
```
Index: 0
```

Hints

Use left + (right - left) / 2 to avoid overflow
If nums[mid] == target, return mid
If nums[mid] < target, search right half: left = mid + 1
If nums[mid] > target, search left half: right = mid - 1

Validated solution

Reveal Java solution

public class Main {
    static int search(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) {
        System.out.println("Index: " + search(new int[] {1, 3, 5, 7, 9, 11}, 9));
    }
}

How to approach the problem

The sorted-order precondition lets a comparison eliminate half of the remaining range. low and high are inclusive bounds, so both move past middle after a failed comparison.

Approach

State the sorted ascending precondition.
Calculate the middle without adding two large indices.
Discard the half that cannot contain target.

Time and space complexity

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

Edge cases to test

A target absent from a one-element array returns -1.
Duplicates need an explicit first/last occurrence rule.

Common mistakes

Using low < high and skipping the final single candidate.
Failing to move a bound past middle.

Follow-up challenge

Search a rotated sorted array by identifying which half is ordered.

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler