Binary Search : Finding Data in O(log n)

Why should you care?

Searching is one of the most common operations in programming.

Suppose you have an array containing 1 million sorted numbers and need to find one particular value.

A simple approach is to check each element:

1 → 2 → 3 → 4 → ...

In the worst case, you may need to check all 1 million elements.

But what if you could eliminate half of the remaining elements after every comparison?

That's exactly what Binary Search does.

Instead of checking every element, Binary Search repeatedly divides the search space in half.

This gives us:

O(log n)

which is dramatically faster than:

O(n)

for large datasets.

---

The Problem

Consider this sorted array:

[10, 20, 30, 40, 50, 60, 70, 80, 90]

We want to find:

70

A linear search checks:

10
20
30
40
50
60
70

That's 7 comparisons.

Binary Search takes a different approach.

Start with the middle:

[10, 20, 30, 40, 50, 60, 70, 80, 90]
                    ↑
                   50

We compare:

70 > 50

Therefore, we know the answer cannot be in the left half.

We discard:

10 20 30 40 50

Now search:

60 70 80 90

Check the middle:

60 70 80 90
   ↑
   70

We found it.

Instead of examining every element, we eliminated large portions of the array at each step.

---

The Concept

Binary Search works by maintaining a search range:

left
right

At every step:

1. Find the middle element.
2. Compare it with the target.
3. If it matches, return the result.
4. If the target is smaller, search the left half.
5. If the target is larger, search the right half.
6. Repeat until the search range becomes empty.

The fundamental operation is:

middle = (left + right) / 2

A safer version in Java is:

int mid = left + (right - left) / 2;

This avoids integer overflow when left and right are very large.

---

Simple Explanation

Imagine you're guessing a number between:

1 and 100

Someone tells you:

"I'm thinking of a number."

You could guess:

1
2
3
4
5
...

That is essentially linear search.

Instead, guess:

50

If they say:

"Too low."

You immediately know the answer is between:

51 and 100

Now guess:

75

If they say:

"Too high."

You know the answer is between:

51 and 74

Every guess removes roughly half the possibilities.

That's Binary Search.

---

Real-world Analogy

Imagine searching for a word in a physical dictionary.

You don't open the dictionary at the first page and read every word.

You open somewhere near the middle.

Suppose you're looking for:

"programming"

but you land around:

"machine"

Since programming comes after machine alphabetically, you ignore everything before that point.

You open the middle of the remaining section.

Then repeat.

Entire dictionary
       ↓
    Half left
       ↓
    Half left
       ↓
    Half left
       ↓
      ...

This is Binary Search.

The dictionary works because its words are sorted.

And that's the most important requirement for traditional Binary Search:

The search space must have an ordering that lets you eliminate half of it.

---

Code Example

Let's implement Binary Search in Java.

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

    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Example:

public static void main(String[] args) {

    int[] numbers = {
        10, 20, 30, 40, 50,
        60, 70, 80, 90
    };

    int result = binarySearch(numbers, 70);

    System.out.println(result);
}

Output:

6

Because:

numbers[6] = 70

---

Understanding the Algorithm Step by Step

Suppose:

arr = [10, 20, 30, 40, 50, 60, 70, 80, 90]
target = 70

Initially:

left = 0
right = 8

Calculate:

mid = 0 + (8 - 0) / 2
    = 4

So:

arr[4] = 50

Compare:

70 > 50

Therefore:

left = mid + 1

Now:

left = 5
right = 8

Next middle:

mid = 6

And:

arr[6] = 70

Target found.

---

Why Is It O(log n)?

Suppose we have:

n = 1,000,000

elements.

Binary Search repeatedly divides the search space:

1,000,000
    ↓
500,000
    ↓
250,000
    ↓
125,000
    ↓
62,500
    ↓
31,250
    ↓
...
    ↓
1

The number of times we can divide n by 2 before reaching 1 is approximately:

log₂(n)

Therefore:

Binary Search = O(log n)

For one million elements, that means only around 20 divisions in the worst case.

Compare that with linear search:

Linear Search  → O(n)
Binary Search  → O(log n)

This difference becomes enormous as n grows.

---

Common Mistakes

Mistake 1: Using Binary Search on unsorted data

Consider:

[50, 10, 80, 30, 70]

There is no useful ordering.

If we inspect 80 and the target is 30, we cannot safely conclude which half contains the target.

Binary Search depends on being able to eliminate a portion of the search space.

For a standard array implementation, sorting is therefore a prerequisite.

---

Mistake 2: Updating the boundaries incorrectly

Suppose:

if (arr[mid] < target) {
    left = mid;
}

This can cause the algorithm to repeatedly examine the same middle element.

Usually we need:

left = mid + 1;

Similarly:

right = mid - 1;

The searched middle element has already been examined, so it should be excluded from the next range.

---

Mistake 3: Using (left + right) / 2 blindly

You will often see:

int mid = (left + right) / 2;

It works for normal-sized arrays.

But if left + right exceeds the maximum integer value, integer overflow can occur.

Prefer:

int mid = left + (right - left) / 2;

This is a small implementation detail, but it is a good habit.

---

Mistake 4: Forgetting the target may not exist

Consider:

[10, 20, 30, 40, 50]

and search for:

35

The algorithm eventually reaches an empty search range.

Therefore, we need:

return -1;

or another appropriate "not found" result.

---

Mistake 5: Assuming Binary Search is always better

Binary Search has a major requirement:

The data must be ordered in a searchable way.

If you have an unsorted array and only need one search, sorting it first may cost:

O(n log n)

That may not be worth doing.

If you're going to perform thousands of searches, however, sorting once and then using Binary Search can be very beneficial.

---

Advanced Notes

1. Recursive Binary Search

Binary Search can also be implemented recursively.

public static int binarySearch(
        int[] arr,
        int left,
        int right,
        int target) {

    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    }

    if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, right, target);
    }

    return binarySearch(arr, left, mid - 1, target);
}

The time complexity remains:

O(log n)

But the recursive version uses call-stack space:

O(log n)

The iterative version generally uses:

O(1)

additional space.

---

2. Finding the First Occurrence

Suppose the array contains duplicates:

[10, 20, 20, 20, 30]

Searching for:

20

may return any matching position depending on the implementation.

But sometimes we need the first occurrence.

We can continue searching toward the left after finding a match.

public static int firstOccurrence(int[] arr, int target) {

    int left = 0;
    int right = arr.length - 1;
    int result = -1;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {

            result = mid;
            right = mid - 1;

        } else if (arr[mid] < target) {

            left = mid + 1;

        } else {

            right = mid - 1;
        }
    }

    return result;
}

This is still:

O(log n)

---

3. Finding the Last Occurrence

We can do the opposite.

When we find the target, continue searching toward the right:

if (arr[mid] == target) {
    result = mid;
    left = mid + 1;
}

This allows Binary Search to solve more than simple "does this value exist?" problems.

---

4. Lower Bound and Upper Bound

Binary Search can be generalized to find boundaries.

For example:

[1, 2, 2, 2, 4, 5]

We can find:

• First position where value is ≥ target
• First position where value is > target

These ideas are commonly called:

Lower Bound
Upper Bound

They are extremely useful in competitive programming and algorithmic problem solving.

---

5. Binary Search on the Answer

Binary Search isn't limited to searching arrays.

Sometimes the search space is a range of possible answers.

Suppose the question is:

What is the minimum capacity required to complete a task within k days?

You might have:

minimum possible answer
        ↓
maximum possible answer

If you can determine whether a particular capacity is sufficient, you can binary-search the answer space.

This technique is called Binary Search on Answer.

It is one of the most important advanced applications of Binary Search.

---

6. Complexity

For an array containing n elements:

Operation	Complexity
Best-case search	O(1)
Worst-case search	O(log n)
Average-case search	O(log n)
Iterative space	O(1)
Recursive space	O(log n)

The key improvement is:

O(n) → O(log n)

when the search space can be repeatedly halved.

---

The Bigger Picture

Binary Search connects directly to the Big-O concept from the previous article.

We learned:

O(n)

means the work grows linearly.

Binary Search gives us:

O(log n)

because each operation removes approximately half of the remaining search space.

It also connects to the data structures we've already studied.

Array

Arrays provide efficient indexing:

arr[index]

which is:

O(1)

When the array is sorted, we can combine that efficient access with Binary Search.

Binary Search Tree

A Binary Search Tree uses a similar idea:

smaller values → left
larger values  → right

At every step, we choose a direction based on comparison.

So Binary Search and Binary Search Trees share the same fundamental strategy:

Use ordering to eliminate unnecessary possibilities.

Tries

Our previous topic, Trie, also reduces the search space by following the relevant characters.

Different data structures solve different search problems, but the underlying principle is similar:

Don't search what you already know cannot contain the answer.

---

The Most Important Mental Model

Don't think of Binary Search as:

"Look at the middle element."

The deeper idea is:

"Every comparison should eliminate as much of the search space as possible."

The middle element is simply the best choice when the search space is ordered and the two sides are roughly equal.

Visualize:

Before:

[ 1  2  3  4  5  6  7  8  9 ]
              ↑
             mid

After one comparison:

[ 6  7  8  9 ]

Then:

[ 6  7  8  9 ]
      ↑
     mid

After another comparison:

[ 6  7 ]

And continue.

The algorithm is powerful because one comparison destroys an entire portion of the search space.

---

Summary

Binary Search is an efficient searching algorithm that works by repeatedly dividing an ordered search space in half.

Key ideas:

• The search space must be ordered or otherwise partitionable.
• Maintain left and right boundaries.
• Calculate the middle position.
• Compare the middle element with the target.
• Discard the impossible half.
• Repeat until the target is found or the range becomes empty.
• Worst-case time complexity is O(log n).
• Iterative Binary Search uses O(1) additional space.
• It can be extended to find first/last occurrences and boundaries.
• Binary Search can also be applied to an abstract range of possible answers.

The fundamental comparison is:

Linear Search → O(n)
Binary Search → O(log n)

For a million sorted elements, that difference can mean checking roughly:

1,000,000

elements versus roughly:

20

steps.