Chapter 13 of 65

Binary Search

On this page

Let's play a small game. I am thinking of a number between 1 and 100. Every time you guess, I will tell you whether my number is higher or lower.

You could guess 1, 2, 3, 4... one by one. That is linear search, and in the worst case it takes 100 guesses.

But a smart player starts with 50.

Guess 50 → "Higher"   → the number is in 51..100
Guess 75 → "Lower"    → the number is in 51..74
Guess 62 → "Higher"   → the number is in 63..74
...

Every guess throws away half of the remaining numbers. With this strategy you will always find the number in at most 7 guesses.

That strategy is Binary Search, one of the most important algorithms in all of DSA.

In the previous chapter, we saw that linear search checks elements one by one and takes O(n) time. Binary search uses one extra piece of information, that the data is sorted, to bring that down to O(log n).


Binary Search is a searching algorithm for sorted data that repeatedly compares the target with the middle element and discards the half in which the target cannot be present.

The word binary means "two". At every step, the search space is split into two halves, and we keep only one of them.

At every step there are only three possibilities:

middle == target  → Found
middle <  target  → Target can only be on the RIGHT side
middle >  target  → Target can only be on the LEFT side

The One Rule: Data Must Be Sorted

Binary search only works because the data is in order.

Look at this sorted array:

[3, 8, 15, 23, 42, 56, 71, 89]

If the middle element is 23 and we are looking for 56, we know for sure that 56 cannot be on the left, because everything on the left is smaller than 23.

Now look at an unsorted array:

[42, 3, 89, 15, 56, 8, 71, 23]

If the middle is 15, it tells us nothing. 56 could be on either side. Throwing away half the array could throw away the answer.

Binary search on unsorted data can silently give wrong answers. Always make sure the data is sorted first.


How Binary Search Works

We keep two pointers:

  • low → the start of the current search range

  • high → the end of the current search range

and compute the middle:

mid = (low + high) / 2      (we will improve this formula soon)

Example 1: Searching for 56

Index:   0   1   2   3   4   5   6   7
Value:   3   8  15  23  42  56  71  89

Step 1

low = 0, high = 7
mid = (0 + 7) / 2 = 3   → arr[3] = 23

23 < 56  → target is on the right
low = mid + 1 = 4
Index:   0   1   2   3 | 4   5   6   7
         ✗   ✗   ✗   ✗ | 42  56  71  89

Step 2

low = 4, high = 7
mid = (4 + 7) / 2 = 5   → arr[5] = 56

56 == 56 → Found at index 5

We found the element in just 2 comparisons. Linear search would have needed 6.

Example 2: Searching for 20 (Not Present)

low=0, high=7 → mid=3 → arr[3]=23 → 23 > 20 → high = 2
low=0, high=2 → mid=1 → arr[1]=8  → 8 < 20  → low  = 2
low=2, high=2 → mid=2 → arr[2]=15 → 15 < 20 → low  = 3
low=3, high=2 → low > high → stop → return -1

When low becomes greater than high, the search range is empty. The target is not in the array.

Notice that we use mid + 1 and mid - 1, not mid. We have already checked arr[mid], so there is no reason to keep it in the range.


Iterative Binary Search in Java

class Main {

    static int binarySearch(int[] arr, int target) {

        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {

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

            if (arr[mid] == target) {
                return mid;                 // found
            } else if (arr[mid] < target) {
                low = mid + 1;              // search the right half
            } else {
                high = mid - 1;             // search the left half
            }
        }

        return -1;                          // not found
    }

    public static void main(String[] args) {

        int[] arr = {3, 8, 15, 23, 42, 56, 71, 89};

        System.out.println("Index of 56: " + binarySearch(arr, 56));
        System.out.println("Index of 3: " + binarySearch(arr, 3));
        System.out.println("Index of 89: " + binarySearch(arr, 89));
        System.out.println("Index of 20: " + binarySearch(arr, 20));
    }
}

Output:

Index of 56: 5
Index of 3: 0
Index of 89: 7
Index of 20: -1

Pay attention to the loop condition: low <= high. When low == high, there is still one element left to check. Using low < high here would skip it.


Why low + (high - low) / 2?

The simple formula (low + high) / 2 has a hidden bug.

In Java, an int can hold values only up to 2,147,483,647. If low and high are both large, their sum can go beyond that limit and overflow into a negative number.

int low = 1_500_000_000;
int high = 2_000_000_000;
System.out.println("(low + high) / 2       = " + (low + high) / 2);
System.out.println("low + (high - low) / 2 = " + (low + (high - low) / 2));

Output:

(low + high) / 2       = -397483648
low + (high - low) / 2 = 1750000000

A negative mid would crash the program with an ArrayIndexOutOfBoundsException.

The formula low + (high - low) / 2 gives the same middle, but high - low never overflows when both are valid indexes. This exact bug existed in Java's own Arrays.binarySearch for years before it was fixed in 2006, so interviewers love asking about it.


Binary search also has a natural recursive form (see the Recursion chapter). Each call works on a smaller range.

static int binarySearch(int[] arr, int target, int low, int high) {

    if (low > high) {
        return -1;                      // base case: empty range
    }

    int mid = low + (high - low) / 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);
    }
}

Calling it:

int[] arr = {3, 8, 15, 23, 42, 56, 71, 89};

System.out.println(binarySearch(arr, 71, 0, arr.length - 1));
System.out.println(binarySearch(arr, 10, 0, arr.length - 1));

Output:

6
-1

The recursive version uses O(log n) stack space. The iterative version uses O(1), so it is usually preferred.


Time and Space Complexity

Each step cuts the search space in half:

n → n/2 → n/4 → n/8 → ... → 1

How many times can we halve n before only one element is left? About log₂ n times. (We saw this pattern in the Time Complexity chapter when we discussed O(log n).)

More precisely, binary search makes at most ⌊log₂ n⌋ + 1 comparisons with the middle element.

Number of elements (n)

Linear search (worst)

Binary search (worst)

100

100

7

1,000

1,000

10

1,000,000

1,000,000

20

1,000,000,000

1,000,000,000

30

Searching one billion sorted numbers in just 30 steps — that is the power of O(log n).

Case

Time

Best (target is the first middle)

O(1)

Average

O(log n)

Worst

O(log n)

Space (iterative)

O(1)

Space (recursive)

O(log n)

Binary search needs random access (jumping straight to the middle in O(1)). That is why it works on arrays but not efficiently on linked lists, where reaching the middle takes O(n).


Binary Search with Duplicates

What if the target appears more than once?

Index:  0  1  2  3  4  5  6  7
Value:  2  4  4  4  7  9  9  12

The basic binary search will return some index of 4, but not necessarily the first or the last one. Many problems need a specific one, so we use small variations.

First Occurrence

When we find the target, we save the index and keep searching on the left, in case there is an earlier copy:

static int firstOccurrence(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int answer = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            answer = mid;        // record it...
            high = mid - 1;      // ...but keep looking on the left
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return answer;
}

Last Occurrence

Same idea, but after a match we keep searching on the right: replace high = mid - 1 with low = mid + 1 in the match branch.

Counting Occurrences in O(log n)

count = lastOccurrence - firstOccurrence + 1     (if the target exists)

For the array above: 3 - 1 + 1 = 3 copies of 4.


Lower Bound and Upper Bound

These two variations are used everywhere in competitive programming and interviews.

  • Lower bound → the first index where arr[i] >= target

  • Upper bound → the first index where arr[i] > target

Index:  0  1  2  3  4  5  6  7
Value:  2  4  4  4  7  9  9  12

lower bound of 9 → index 5   (first value >= 9)
upper bound of 9 → index 7   (first value >  9)

A very useful property: if the target is not present, the lower bound is exactly the position where it should be inserted to keep the array sorted. This is the classic Search Insert Position problem.


Complete Example: Binary Search Variations

import java.util.Arrays;

class Main {

    // First index where arr[i] == target, or -1
    static int firstOccurrence(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int answer = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                answer = mid;        // record it...
                high = mid - 1;      // ...but keep looking on the left
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return answer;
    }

    // Last index where arr[i] == target, or -1
    static int lastOccurrence(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int answer = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                answer = mid;        // record it...
                low = mid + 1;       // ...but keep looking on the right
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return answer;
    }

    // Lower bound: first index where arr[i] >= target
    // (returns arr.length if every element is smaller)
    static int lowerBound(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int answer = arr.length;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= target) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return answer;
    }

    // Upper bound: first index where arr[i] > target
    static int upperBound(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int answer = arr.length;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > target) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {

        int[] arr = {2, 4, 4, 4, 7, 9, 9, 12};
        System.out.println("Array: " + Arrays.toString(arr));

        System.out.println("First 4: " + firstOccurrence(arr, 4));
        System.out.println("Last 4: " + lastOccurrence(arr, 4));
        int first = firstOccurrence(arr, 4);
        int count = (first == -1) ? 0 : lastOccurrence(arr, 4) - first + 1;
        System.out.println("Count of 4: " + count);

        System.out.println("Lower bound of 9: " + lowerBound(arr, 9));
        System.out.println("Upper bound of 9: " + upperBound(arr, 9));
        System.out.println("Insert position of 8: " + lowerBound(arr, 8));
        System.out.println("Insert position of 20: " + lowerBound(arr, 20));
    }
}

Output:

Array: [2, 4, 4, 4, 7, 9, 9, 12]
First 4: 1
Last 4: 3
Count of 4: 3
Lower bound of 9: 5
Upper bound of 9: 7
Insert position of 8: 5
Insert position of 20: 8

Notice that upperBound - lowerBound also gives the count: for 9, 7 - 5 = 2.


Binary Search on the Answer

Binary search is not only for finding an element in an array. It can search over a range of possible answers.

The pattern works whenever the answers look like this:

possible answers: 0  1  2  3  4  5  6  7  8 ...
condition true?   ✓  ✓  ✓  ✓  ✓  ✓  ✓  ✗  ✗ ...
                                       ↑
                         we want the last ✓

Once the condition becomes false, it stays false. That "sorted" true/false pattern is all binary search needs.

Example: Integer Square Root

Find the largest integer x such that x * x <= n, without using Math.sqrt().

static int floorSqrt(int n) {
    int low = 0, high = n;
    int answer = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if ((long) mid * mid <= n) {    // long avoids overflow
            answer = mid;               // mid works, try bigger
            low = mid + 1;
        } else {
            high = mid - 1;             // mid too big
        }
    }
    return answer;
}

The cast to long matters: for a large mid, mid * mid would overflow an int.

This "binary search on answer" idea solves many famous interview problems, such as Koko Eating Bananas, Capacity to Ship Packages, Aggressive Cows and Book Allocation.


Search in a Rotated Sorted Array

A sorted array is sometimes "rotated" at an unknown point:

Original: [10, 20, 30, 40, 50, 60]
Rotated:  [40, 50, 60, 10, 20, 30]

The whole array is no longer sorted, but there is a key observation:

When you split a rotated sorted array at the middle, at least one half is always sorted.

So at each step we check which half is sorted, then check whether the target lies inside that sorted half's range. If it does, we go there; otherwise we go to the other half.

static int searchRotated(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[low] <= arr[mid]) {             // left half is sorted
            if (target >= arr[low] && target < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {                                // right half is sorted
            if (target > arr[mid] && target <= arr[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

Tracing a search for 20 in [40, 50, 60, 10, 20, 30]:

low=0, high=5 → mid=2 → arr[2]=60
left half [40, 50, 60] is sorted, 20 is not in 40..60 → low = 3

low=3, high=5 → mid=4 → arr[4]=20 → Found at index 4

This version assumes all elements are distinct. It still runs in O(log n).


Java already provides binary search:

// needs: import java.util.Arrays; at the top of the file

int[] arr = {3, 8, 15, 23, 42, 56, 71, 89};
System.out.println("Arrays.binarySearch(arr, 42) = " + Arrays.binarySearch(arr, 42));
System.out.println("Arrays.binarySearch(arr, 20) = " + Arrays.binarySearch(arr, 20));

Output:

Arrays.binarySearch(arr, 42) = 4
Arrays.binarySearch(arr, 20) = -4

Why -4? When the key is not found, Java returns -(insertionPoint) - 1. Here 20 would be inserted at index 3, so the result is -3 - 1 = -4. This guarantees that the result is negative only when the key is missing.

Two things to remember about Arrays.binarySearch (and Collections.binarySearch for lists):

  • The array must be sorted, otherwise the result is undefined.

  • If there are duplicates, there is no guarantee which copy's index is returned. Use your own first/last occurrence code when that matters.


Common Mistakes

1. Using Binary Search on Unsorted Data

It will not throw an error. It can just quietly give wrong answers. Always check that the input is sorted.

2. Wrong Loop Condition

With the low = mid + 1 / high = mid - 1 style used in this chapter, the condition must be while (low <= high). Using < misses the case where one element is left.

3. Infinite Loops from low = mid

// WRONG
low = mid;     // if low == mid, the range never shrinks

Suppose low = 4 and high = 5. Then mid = 4. If we set low = mid, low stays 4 forever. Always move past mid once it has been checked.

4. Integer Overflow

Use low + (high - low) / 2 for mid, and use long when multiplying in "binary search on answer" problems.

5. Using It on a Linked List

Binary search needs O(1) access to the middle element. On a linked list, reaching the middle costs O(n), which destroys the benefit.


Feature

Linear Search

Binary Search

Data must be sorted?

No

Yes

Worst-case time

O(n)

O(log n)

Best-case time

O(1)

O(1)

Extra space

O(1)

O(1) iterative

Works on linked lists?

Yes

Not efficiently

Best for

Small or unsorted data, one-time searches

Large sorted data, repeated searches

If your data is unsorted and you need to search it many times, it can be worth sorting it once (sorting is the topic of the next chapter) and then using binary search for every query.


Interview Tips and Practice Problems

Whenever you see any of these clues in a problem, think of binary search:

  • The input array is sorted (or rotated sorted)

  • The problem asks for O(log n) time

  • You need the minimum or maximum value that satisfies some condition

  • The answer lies in a numeric range and you can quickly check whether a guess works

Practice problems, roughly from easy to hard:

  • Binary Search (basic)

  • Search Insert Position

  • First and Last Position of Element in Sorted Array

  • Sqrt(x)

  • Find Peak Element

  • Search in Rotated Sorted Array

  • Find Minimum in Rotated Sorted Array

  • Koko Eating Bananas

  • Search a 2D Matrix

  • Median of Two Sorted Arrays (hard)

A tip for interviews: before writing code, say out loud what low, high and answer mean, and when the loop stops. Most binary search bugs come from being unclear about these boundaries.


The Main Idea

Binary Search finds an element in sorted data by checking the middle and discarding half of the remaining elements every time.

low = 0, high = n - 1
        ↓
while low <= high
        ↓
mid = low + (high - low) / 2
        ↓
arr[mid] == target → return mid
arr[mid] <  target → low  = mid + 1
arr[mid] >  target → high = mid - 1
        ↓
return -1

The facts to remember:

Requirement  → sorted data with random access
Time         → O(log n)
Space        → O(1) iterative, O(log n) recursive
Variations   → first/last occurrence, lower/upper bound,
               binary search on answer, rotated arrays

Binary search turns a search over a billion elements into about 30 steps — but only because the data is sorted. That is one big reason sorting is so important, and it is exactly what we study next.