Binary Search Program in Java

What is binary search

Binary search is a fast way to find a value in a sorted array. Instead of checking every item, it looks at the middle, then throws away the half that cannot contain the target. Repeating this halving finds the item in very few steps.

The halving idea

To find 7 in {1, 3, 5, 7, 9, 11}: look at the middle (5). Since 7 > 5, the answer must be in the right half, so we ignore the left. We repeat on the smaller range until we land on 7. Each step cuts the work in half.

The Java program

public class BinarySearch {
    public static void main(String[] args) {
        int[] a = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int low = 0, high = a.length - 1, pos = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == target) { pos = mid; break; }
            else if (a[mid] < target) low = mid + 1;   // go right
            else high = mid - 1;                       // go left
        }
        System.out.println(pos == -1 ? "Not found" : "Found at " + pos);
    }
}

We keep a low and high range and check the middle. If the middle is too small we move low right; too big, we move high left. We stop when found or the range is empty.

Dry run

Why sorted is required

Binary search decides which half to keep by comparing the target with the middle value. That only works if everything left of the middle is smaller and everything right is larger — that is, the array is sorted. On an unsorted array, discarding a half could remove the very item you are looking for, giving wrong results.

Time complexity

• Binary search: O(log n) — halves the range each step (needs sorted data).
• Linear search: O(n) — checks each item (works on any array).
• Space: O(1) — just a few variables.

For a million sorted items, binary search needs about 20 steps versus up to a million for linear search.

Common mistakes

• Using it on an unsorted array. Sort first, or the result is wrong.
• Wrong mid formula. Use low + (high - low) / 2 to avoid overflow.
• Off-by-one on low/high. Move to mid + 1 or mid - 1, not mid.
• Wrong loop condition. Use low <= high, or you miss the last element.

Summary

• Binary search finds a value in a sorted array by halving the range.
• Check the middle, then keep the half that can contain the target.
• The array must be sorted for it to work.
• Use mid = low + (high - low) / 2 to avoid overflow.
• It is O(log n) — far faster than linear search on large sorted data.

Next, sort the data first with bubble sort, or revise Java arrays.