Binary Search Algorithm Explained

Binary Search is an efficient searching algorithm that finds a target value inside a sorted array by repeatedly dividing the search range in half. Instead of checking elements one by one, it compares the target with the middle element and decides whether to continue searching in the left half or the right half.

Binary Search is much faster than Linear Search for large sorted datasets. Its time complexity is O(log n), which means the number of required checks grows very slowly even when the input size becomes large.

Introduction

Searching is one of the most common operations in programming. Developers often need to find a specific number, user, product, record, ID, date, or value inside a collection of data.

Linear Search is the simplest way to search because it checks elements one by one. However, when the data is large, checking every element can become slow. Binary Search solves this problem by using an important condition: the data must be sorted.

When the array is sorted, Binary Search can ignore half of the remaining elements after each comparison. This makes it one of the most important algorithms for learning efficient search, logarithmic time complexity, and divide-and-conquer thinking.

What Is Binary Search?

Binary Search is a searching algorithm used to find a target value in a sorted array. It works by comparing the target value with the middle element of the current search range.

If the middle element is equal to the target, the search is complete. If the target is smaller than the middle element, the algorithm continues searching in the left half. If the target is greater than the middle element, the algorithm continues searching in the right half.

The main idea is simple:

Start with the full sorted array.
Find the middle element.
Compare the middle element with the target.
If the target is found, return its index.
If the target is smaller, search the left half.
If the target is larger, search the right half.
Repeat until the target is found or the search range becomes empty.

Binary Search is called “binary” because each step splits the search space into two parts.

The Most Important Requirement

Binary Search only works correctly when the array is sorted.

For example, this array is sorted:

[2, 4, 6, 8, 10, 12, 14]

Binary Search can work on this array because all values are arranged in ascending order.

But this array is not sorted:

[8, 2, 14, 4, 10, 6, 12]

Binary Search should not be used directly on this array because the algorithm depends on knowing that smaller values are on the left and larger values are on the right.

If the data is not sorted, developers should either sort it first or use another searching method such as Linear Search.

Why Binary Search Is Important

Binary Search is important because it shows how a simple idea can dramatically improve performance. Instead of checking every value, the algorithm eliminates half of the remaining search space after each comparison.

This means that even a very large array can be searched using only a small number of checks.

For example:

In an array of 16 elements, Binary Search needs at most about 4 checks.
In an array of 1,024 elements, it needs at most about 10 checks.
In an array of 1,000,000 elements, it needs about 20 checks.

This efficiency is why Binary Search is a core algorithm in computer science.

How Binary Search Works

Binary Search keeps track of two boundaries: the left boundary and the right boundary. These boundaries define the current search range.

At each step, the algorithm calculates the middle index:

middle = left + (right - left) / 2

Then it compares the middle value with the target value.

If the middle value is too small, the target must be on the right side. If the middle value is too large, the target must be on the left side. If the middle value matches the target, the algorithm returns the middle index.

This process continues until the search range becomes empty.

Manual Run Example

Let us manually search for the target value 14 in the following sorted array:

[2, 4, 6, 8, 10, 12, 14, 16, 18]

The target value is:

Target = 14

The array indexes are:

Index:  0  1  2  3   4   5   6   7   8
Value:  2  4  6  8  10  12  14  16  18

Step 1: Set the Initial Boundaries

At the beginning, the left boundary is the first index and the right boundary is the last index.

left = 0
right = 8

Now we calculate the middle index:

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

The middle value is:

array[4] = 10

Compare the middle value with the target:

10 == 14 ? No
10 < 14 ? Yes

Since 10 is smaller than 14, the target must be in the right half.

So we move the left boundary:

left = middle + 1 = 5

Step 2: Search the Right Half

The current search range is now:

[12, 14, 16, 18]

The boundaries are:

left = 5
right = 8

Calculate the middle index:

middle = 5 + (8 - 5) / 2 = 6

The middle value is:

array[6] = 14

Compare the middle value with the target:

14 == 14 ? Yes

The target is found at index 6.

Search Result

Target 14 found at index 6

Binary Search found the target in only two checks. Linear Search would have checked seven elements in this example before reaching 14.

Manual Run When the Value Is Not Found

Now let us search for the target value 15 in the same sorted array:

[2, 4, 6, 8, 10, 12, 14, 16, 18]

The target value is:

Target = 15

Step 1

Initial boundaries:

left = 0
right = 8

Middle index:

middle = 4

Middle value:

array[4] = 10

Since 10 is smaller than 15, search the right half:

left = 5
right = 8

Step 2

Current search range:

[12, 14, 16, 18]

Middle index:

middle = 6

Middle value:

array[6] = 14

Since 14 is smaller than 15, search the right half:

left = 7
right = 8

Step 3

Current search range:

[16, 18]

Middle index:

middle = 7

Middle value:

array[7] = 16

Since 16 is greater than 15, search the left half:

left = 7
right = 6

Now the left boundary is greater than the right boundary. This means the search range is empty.

Search Result

Target 15 was not found

The algorithm stops because there is no remaining part of the array to search.

Binary Search Algorithm Steps

The iterative Binary Search algorithm follows these steps:

Receive a sorted array and a target value.
Set left to 0.
Set right to the last index of the array.
While left is less than or equal to right, calculate the middle index.
If the middle value equals the target, return the middle index.
If the middle value is less than the target, move left to middle + 1.
If the middle value is greater than the target, move right to middle - 1.
If the loop ends, return -1 because the target was not found.

This version does not require recursion and is often the easiest version to use in practical code.

Pseudocode

binarySearch(array, target):
    left = 0
    right = length(array) - 1

    while left <= right:
        middle = left + (right - left) / 2

        if array[middle] == target:
            return middle

        if array[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

The function returns the index of the target value if it exists. If the target does not exist, it returns -1.

Binary Search Example in PHP

Here is a clean iterative PHP implementation of Binary Search:

<?php

function binarySearch(array $numbers, int $target): int
{
    $left = 0;
    $right = count($numbers) - 1;

    while ($left <= $right) {
        $middle = $left + intdiv($right - $left, 2);

        if ($numbers[$middle] === $target) {
            return $middle;
        }

        if ($numbers[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return -1;
}

$numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

echo binarySearch($numbers, 14);

The output will be:

The target value 14 exists at index 6, so the function returns 6.

Binary Search in PHP When Value Is Not Found

If we search for a value that does not exist:

<?php

$numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

echo binarySearch($numbers, 15);

The output will be:

-1

The value 15 does not exist in the array, so the function returns -1.

Binary Search Example in JavaScript

Here is the same algorithm implemented in JavaScript:

function binarySearch(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left <= right) {
        const middle = left + Math.floor((right - left) / 2);

        if (numbers[middle] === target) {
            return middle;
        }

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

    return -1;
}

const numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

console.log(binarySearch(numbers, 14));

The output will be:

The JavaScript version follows the same logic as the PHP version. It repeatedly checks the middle value and removes half of the search range.

Recursive Binary Search

Binary Search can also be implemented recursively. In the recursive version, the function calls itself with a smaller search range.

The recursive idea is:

If the range is empty, return -1.
Check the middle element.
If the target is found, return the middle index.
If the target is smaller, recursively search the left half.
If the target is larger, recursively search the right half.

The recursive version is elegant, but the iterative version is usually more memory-efficient because it does not create recursive call stack frames.

Recursive Binary Search in PHP

<?php

function recursiveBinarySearch(array $numbers, int $target, int $left, int $right): int
{
    if ($left > $right) {
        return -1;
    }

    $middle = $left + intdiv($right - $left, 2);

    if ($numbers[$middle] === $target) {
        return $middle;
    }

    if ($numbers[$middle] > $target) {
        return recursiveBinarySearch($numbers, $target, $left, $middle - 1);
    }

    return recursiveBinarySearch($numbers, $target, $middle + 1, $right);
}

$numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

echo recursiveBinarySearch($numbers, 14, 0, count($numbers) - 1);

The output will be:

The recursive function keeps reducing the search range until it finds the target or the range becomes empty.

Recursive Binary Search in JavaScript

function recursiveBinarySearch(numbers, target, left = 0, right = numbers.length - 1) {
    if (left > right) {
        return -1;
    }

    const middle = left + Math.floor((right - left) / 2);

    if (numbers[middle] === target) {
        return middle;
    }

    if (numbers[middle] > target) {
        return recursiveBinarySearch(numbers, target, left, middle - 1);
    }

    return recursiveBinarySearch(numbers, target, middle + 1, right);
}

const numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

console.log(recursiveBinarySearch(numbers, 14));

The output will be:

This version is useful for learning recursion, but the iterative version is often preferred in production code.

Why We Calculate Middle This Way

You may see the middle index calculated like this:

middle = (left + right) / 2

This works for small numbers, but in some programming languages, adding left and right directly can cause integer overflow when the indexes are very large.

A safer formula is:

middle = left + (right - left) / 2

This avoids adding two potentially large indexes together. In PHP and JavaScript examples, we used this safer style.

Time Complexity of Binary Search

Time complexity describes how the running time of an algorithm grows as the input size increases. Binary Search is efficient because each step cuts the search range in half.

Binary Search has the following time complexity:

Best case: O(1)
Average case: O(log n)
Worst case: O(log n)

Where n is the number of elements in the sorted array.

Best Case Time Complexity: O(1)

The best case happens when the target value is found at the middle position on the first check.

Array:  [2, 4, 6, 8, 10]
Target: 6

The middle value is 6, so the algorithm finds the target immediately.

Therefore, the best case time complexity is:

O(1)

This means constant time because only one comparison is needed.

Average Case Time Complexity: O(log n)

The average case happens when the target is not found immediately, but the algorithm keeps eliminating half of the search range.

For example, if the array has 16 elements, the search range becomes:

16 → 8 → 4 → 2 → 1

The number of steps grows logarithmically, not linearly.

Therefore, the average case time complexity is:

O(log n)

Worst Case Time Complexity: O(log n)

The worst case happens when the target is at the last possible checked position or when the target does not exist in the array.

Even in this case, Binary Search does not check every element. It still cuts the search range in half at every step.

For example, with 1,024 elements:

1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

This takes about 10 steps because:

log2(1024) = 10

Therefore, the worst case time complexity is:

O(log n)

Why Binary Search Is O(log n)

Binary Search is O(log n) because every comparison removes half of the remaining elements from consideration.

If the input size doubles, Binary Search usually needs only one extra step.

Elements: 8       Maximum steps: 3
Elements: 16      Maximum steps: 4
Elements: 32      Maximum steps: 5
Elements: 1024    Maximum steps: 10
Elements: 1,048,576 Maximum steps: 20

This slow growth is what makes Binary Search extremely efficient for large sorted datasets.

Space Complexity of Binary Search

Space complexity describes how much extra memory an algorithm uses.

The iterative version of Binary Search uses only a few variables:

left
right
middle
target

It does not create a new array or data structure.

Therefore, the space complexity of iterative Binary Search is:

O(1)

The recursive version uses the call stack. Because the recursion depth is O(log n), the space complexity of recursive Binary Search is:

O(log n)

Binary Search vs Linear Search

Binary Search and Linear Search are both searching algorithms, but they are used in different situations.

Linear Search checks elements one by one. Binary Search repeatedly divides the search range in half.

Main differences include:

Linear Search works on unsorted data.
Binary Search requires sorted data.
Linear Search has worst-case time complexity O(n).
Binary Search has worst-case time complexity O(log n).
Linear Search is simpler.
Binary Search is much faster for large sorted arrays.

If the array is small or unsorted, Linear Search may be enough. If the array is large and sorted, Binary Search is usually much better.

Binary Search with Duplicate Values

If the sorted array contains duplicate values, normal Binary Search may return any one of the matching indexes, not necessarily the first or last occurrence.

For example:

Array:  [2, 4, 4, 4, 6, 8]
Target: 4

Binary Search may return index 1, 2, or 3 depending on how the middle index is calculated during the search.

If developers need the first occurrence or last occurrence, the algorithm must be modified.

Finding the First Occurrence

To find the first occurrence of a duplicate value, we continue searching on the left side even after finding the target.

<?php

function firstOccurrence(array $numbers, int $target): int
{
    $left = 0;
    $right = count($numbers) - 1;
    $result = -1;

    while ($left <= $right) {
        $middle = $left + intdiv($right - $left, 2);

        if ($numbers[$middle] === $target) {
            $result = $middle;
            $right = $middle - 1;
        } elseif ($numbers[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return $result;
}

$numbers = [2, 4, 4, 4, 6, 8];

echo firstOccurrence($numbers, 4);

The output will be:

This version stores the found index and continues searching left to see if an earlier occurrence exists.

Finding the Last Occurrence

To find the last occurrence, we continue searching on the right side after finding the target.

<?php

function lastOccurrence(array $numbers, int $target): int
{
    $left = 0;
    $right = count($numbers) - 1;
    $result = -1;

    while ($left <= $right) {
        $middle = $left + intdiv($right - $left, 2);

        if ($numbers[$middle] === $target) {
            $result = $middle;
            $left = $middle + 1;
        } elseif ($numbers[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return $result;
}

$numbers = [2, 4, 4, 4, 6, 8];

echo lastOccurrence($numbers, 4);

The output will be:

This version stores the found index and continues searching right to find the last matching position.

Binary Search on Descending Arrays

Binary Search can also work on arrays sorted in descending order, but the comparison logic must be reversed.

For example:

[18, 16, 14, 12, 10, 8, 6, 4, 2]

In an ascending array, if the middle value is smaller than the target, we search right. In a descending array, if the middle value is smaller than the target, we search left.

This is why developers must know the sorting direction before applying Binary Search.

Binary Search on Answer

Binary Search is not only used to find an element in an array. It can also be used to find an answer in a numeric range when the problem has a monotonic condition.

A monotonic condition means that once a condition becomes true, it stays true after that point, or once it becomes false, it stays false after that point.

Examples include:

Finding the minimum capacity needed to ship packages within a number of days.
Finding the smallest speed required to finish a task before a deadline.
Finding the first bad version in a sequence of versions.
Finding a lower bound or upper bound in a sorted range.

This technique is often called “Binary Search on Answer” and is common in problem solving and competitive programming.

Lower Bound and Upper Bound

Binary Search can be modified to find boundaries instead of exact values.

Lower bound usually means the first position where a value can be inserted without breaking sorted order. It finds the first element greater than or equal to the target.

Upper bound usually means the first position greater than the target.

These variants are useful when working with duplicates, ranges, sorted lists, and insertion positions.

When Should Developers Use Binary Search?

Developers should use Binary Search when the data is sorted and fast searching is needed.

Binary Search is useful when:

The array is sorted.
The dataset is large.
Search operations happen frequently.
Random access by index is available.
The search problem can be divided into halves.
A logarithmic solution is needed.
The problem has a monotonic condition.

Binary Search is especially powerful when searching large sorted arrays or solving range-based algorithmic problems.

When Not to Use Binary Search

Binary Search should not be used when the data is unsorted and sorting it first is not worth the cost.

Developers should avoid Binary Search when:

The array is not sorted.
The dataset is very small and Linear Search is simpler.
The data structure does not support fast random access.
The comparison rule is not consistent.
The data changes constantly and keeping it sorted is expensive.

If the data is unsorted and only one search is needed, Linear Search may be more practical than sorting first and then applying Binary Search.

Practical Example: Searching Product Prices

Imagine an e-commerce system with a sorted list of product prices. If we need to check whether a specific price exists, Binary Search can do it efficiently.

<?php

$prices = [19, 29, 49, 79, 99, 149, 199];

echo binarySearch($prices, 79);

The output will be:

The price 79 exists at index 3.

Practical Example: Searching User IDs

If user IDs are stored in sorted order, Binary Search can quickly check whether a specific ID exists.

User IDs:
[101, 105, 109, 120, 135, 150, 180]

Target:
135

Binary Search can find 135 without checking every ID one by one.

In real backend systems, database indexes usually handle this kind of search more efficiently. However, the idea behind indexed search is related to avoiding full linear scans whenever possible.

Common Mistakes When Implementing Binary Search

Binary Search is simple in concept, but many developers make mistakes when implementing it.

Common mistakes include:

Using Binary Search on an unsorted array.
Using the wrong loop condition.
Forgetting to update left or right.
Using middle again instead of middle + 1 or middle - 1.
Creating an infinite loop.
Calculating the middle index incorrectly.
Not handling empty arrays.
Expecting a normal Binary Search to always return the first duplicate.

The most important rule is to shrink the search range correctly after every comparison.

Practical Checklist for Understanding Binary Search

Before moving to advanced search problems, developers should be able to answer these questions:

Why must the array be sorted?
What do left and right represent?
How is the middle index calculated?
When should the algorithm search the left half?
When should the algorithm search the right half?
What is the stopping condition?
Why is the time complexity O(log n)?
What is the difference between iterative and recursive Binary Search?
How should duplicates be handled?

If these questions are clear, the developer understands Binary Search deeply instead of only memorizing the code.

Advantages of Binary Search

Binary Search has several important advantages.

It is very efficient for large sorted arrays.
It has O(log n) average and worst-case time complexity.
It uses O(1) extra memory in the iterative version.
It is easy to adapt for first occurrence, last occurrence, lower bound, and upper bound.
It teaches logarithmic thinking and divide-and-conquer logic.
It is useful in many algorithmic problems beyond simple searching.

These advantages make Binary Search one of the most important algorithms for developers to master.

Disadvantages of Binary Search

Binary Search also has limitations.

It requires sorted data.
It is more complex than Linear Search.
It is not ideal for data structures without fast index access.
It may require sorting first, which has its own cost.
It can be implemented incorrectly if boundary updates are wrong.

Because of these limitations, Binary Search is powerful only when its requirements are satisfied.

Binary Search in Real Software Projects

In real software projects, developers usually do not manually implement Binary Search for every search problem. Programming languages, databases, search engines, and libraries often provide optimized search and indexing mechanisms.

However, understanding Binary Search is still valuable because the same idea appears in many places. Database indexes, sorted collections, range queries, pagination boundaries, version checks, optimization problems, and algorithm challenges often depend on binary search thinking.

For backend developers, Binary Search also helps build stronger intuition about why indexed queries are faster than scanning every record.

Conclusion

Binary Search is an efficient searching algorithm that finds a target value in a sorted array by repeatedly dividing the search range in half.

Its best case time complexity is O(1) when the target is found immediately. Its average and worst-case time complexity is O(log n), which makes it much faster than Linear Search for large sorted datasets.

The most important requirement is that the data must be sorted. Without sorted data, Binary Search cannot reliably decide whether to search the left half or the right half.

Binary Search can be implemented iteratively or recursively. The iterative version uses O(1) extra space, while the recursive version uses O(log n) stack space. The algorithm can also be extended to handle duplicates, lower bounds, upper bounds, and answer-search problems.

For developers learning data structures and algorithms, Binary Search is essential. It teaches efficient searching, boundary control, logarithmic complexity, and the power of reducing a problem by half at every step.

Binary Search Algorithm

Binary Search Algorithm Explained

Introduction

What Is Binary Search?

The Most Important Requirement

Why Binary Search Is Important

How Binary Search Works

Manual Run Example

Step 1: Set the Initial Boundaries

Step 2: Search the Right Half

Search Result

Manual Run When the Value Is Not Found

Step 1

Step 2

Step 3

Search Result

Binary Search Algorithm Steps

Pseudocode

Binary Search Example in PHP

Binary Search in PHP When Value Is Not Found

Binary Search Example in JavaScript

Recursive Binary Search

Recursive Binary Search in PHP

Recursive Binary Search in JavaScript

Why We Calculate Middle This Way

Time Complexity of Binary Search

Best Case Time Complexity: O(1)

Average Case Time Complexity: O(log n)

Worst Case Time Complexity: O(log n)

Why Binary Search Is O(log n)

Space Complexity of Binary Search

Binary Search vs Linear Search

Binary Search with Duplicate Values

Finding the First Occurrence

Finding the Last Occurrence

Binary Search on Descending Arrays

Binary Search on Answer

Lower Bound and Upper Bound

When Should Developers Use Binary Search?

When Not to Use Binary Search

Practical Example: Searching Product Prices

Practical Example: Searching User IDs

Common Mistakes When Implementing Binary Search

Practical Checklist for Understanding Binary Search

Advantages of Binary Search

Disadvantages of Binary Search

Binary Search in Real Software Projects

Conclusion

Most Viewed Articles