Java Program for Binary Search with Example and Explanation

A Java program for binary search uses a while loop to repeatedly divide the sorted array and check the middle element with the target, like int mid = (low + high) / 2; and adjusts low or high until the target is found or the search space is empty.

Examples

Inputarray = {1, 3, 5, 7, 9}, target = 7

OutputTarget found at index 3

Inputarray = {2, 4, 6, 8, 10}, target = 5

OutputTarget not found

Inputarray = {10}, target = 10

OutputTarget found at index 0

How to Think About It

To find a number in a sorted list, start by looking at the middle item. If it matches the number, you are done. If the number is smaller, look only in the left half. If larger, look only in the right half. Repeat this process until you find the number or the list is empty.

Algorithm

1

Start with two pointers: low at the start, high at the end of the array.

2

While low is less than or equal to high:

3

Calculate mid as the average of low and high.

4

If the middle element equals the target, return mid.

5

If the middle element is less than the target, move low to mid + 1.

6

Else, move high to mid - 1.

7

If the loop ends without finding the target, return -1.

Code

java

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9};
        int target = 7;
        int result = binarySearch(array, target);
        if (result == -1) {
            System.out.println("Target not found");
        } else {
            System.out.println("Target found at index " + result);
        }
    }
}

Output

Target found at index 3

Dry Run

Let's trace searching for target 7 in array {1, 3, 5, 7, 9} through the code

1

Initialize pointers

low = 0, high = 4 (array length - 1)

2

Calculate mid

mid = (0 + 4) / 2 = 2, arr[mid] = 5

3

Compare mid element with target

5 < 7, so move low to mid + 1 = 3

4

Calculate new mid

mid = (3 + 4) / 2 = 3, arr[mid] = 7

5

Check if mid element equals target

7 == 7, target found at index 3

low	high	mid	arr[mid]	action
0	4	2	5	5 < 7, move low to 3
3	4	3	7	7 == 7, found target

Why This Works

Step 1: Divide and conquer

The code splits the array into halves by calculating the middle index with mid = (low + high) / 2 to reduce the search space quickly.

Step 2: Compare middle element

It compares the middle element with the target to decide if the target is found or if the search should continue in the left or right half.

Step 3: Adjust search range

If the middle element is less than the target, it moves the low pointer up to search the right half; otherwise, it moves the high pointer down to search the left half.

Step 4: Loop until found or empty

This process repeats until the target is found or the pointers cross, meaning the target is not in the array.

Alternative Approaches

Recursive binary search

java

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int target, int low, int high) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, high);
        else return binarySearch(arr, target, low, mid - 1);
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9};
        int target = 7;
        int result = binarySearch(array, target, 0, array.length - 1);
        if (result == -1) System.out.println("Target not found");
        else System.out.println("Target found at index " + result);
    }
}

Uses recursion instead of a loop; easier to read but uses more stack space.

Using Java Arrays.binarySearch()

java

import java.util.Arrays;
public class BinarySearchBuiltIn {
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9};
        int target = 7;
        int result = Arrays.binarySearch(array, target);
        if (result < 0) System.out.println("Target not found");
        else System.out.println("Target found at index " + result);
    }
}

Built-in method is optimized and simple but hides the algorithm details.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search divides the search space in half each step, so it runs in logarithmic time relative to the array size.

Space Complexity

The iterative version uses constant extra space, only a few variables for pointers and mid calculation.

Which Approach is Fastest?

The built-in Arrays.binarySearch() is fastest and optimized, but iterative and recursive versions are good for learning and customization.

Approach	Time	Space	Best For
Iterative binary search	O(log n)	O(1)	Low memory, clear control flow
Recursive binary search	O(log n)	O(log n)	Clear code, but uses stack space
Java built-in Arrays.binarySearch()	O(log n)	O(1)	Fastest, simplest for production