Java · Course navigation

Java binary search and interval bounds

Implement logarithmic search on an ascending array.

On this page

Before you start

Arrays, loops, and methods.

Implement logarithmic search on an ascending array.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

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.