Java binary search and interval bounds

Implement logarithmic search on an ascending array.

Java

class Main {
    static int search(int[] values, int target) {
        int low = 0, high = values.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (values[mid] == target) return mid;
            if (values[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(search(new int[]{2, 4, 6, 8, 10}, 8));
        System.out.println(search(new int[]{}, 8));
        if (search(new int[]{2, 4}, 3) != -1) throw new AssertionError("missing");
    }
}

Output

3
-1

Explanation

An inclusive interval tracks where the target could still be. Each comparison either returns a match or removes the midpoint and one half of the candidates.

Computing low + (high-low)/2 avoids overflow from directly adding two large nonnegative indices. Empty arrays start with high=-1 and skip the loop.

Explore the dry run

Guided walkthroughReady

1class Main {

2 static int search(int[] values, int target) {

3 int low = 0, high = values.length - 1;

4 while (low <= high) {

5 int mid = low + (high - low) / 2;

6 if (values[mid] == target) return mid;

7 if (values[mid] < target) low = mid + 1;

8 else high = mid - 1;

9 }

10 return -1;

11 }

12 public static void main(String[] args) {

13 System.out.println(search(new int[]{2, 4, 6, 8, 10}, 8));

14 System.out.println(search(new int[]{}, 8));

15 if (search(new int[]{2, 4}, 3) != -1) throw new AssertionError("missing");

16 }

17}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Initialize the first search.	`low = 0, high = 4`	—
Inspect index 2.	`mid = 2, value = 6`	—
Discard the left half because 6 < 8.	`low = 3, high = 4`	—
The next midpoint is 3 and matches 8.	`return = 3`	—
Print the matching index.	`return = 3`	3
An empty interval returns -1.	`return = 3`	3 -1

Cost and common mistakes

O(log n) time and O(1) auxiliary space.

The array must be sorted using the same ordering.
This version returns a match, not necessarily the first duplicate.

Try it yourself

Search for 1 in [2,4,6,8,10].

Reveal answer and reasoning

The interval moves left until empty and returns -1.

Java binary search and interval bounds

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading