Binary Search

Binary Search

Searching for
▲ lo
▲ mid
▲ hi
Comparing
—
0%
Step 0 / 6
Size 14 items
Code
def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

 

Binary search finds a target value in a **sorted** array by repeatedly halving the search window. It compares the middle element with the target: a match ends the search; otherwise, it discards the half that cannot contain the target and shrinks the window to the other half. Each comparison eliminates half of the remaining elements, which is why it runs in O(log n): searching a million sorted values takes at most about 20 comparisons.

The animation above shows the lo, mid and hi pointers and dims the eliminated half after every comparison. The one non-negotiable precondition: the array must already be sorted. On unsorted data, you need linear search or a sort first (see merge sort). The same halving idea powers the binary search tree.

Time & space complexity

CaseComplexityNotes
Best caseO(1)The middle element is the target on the first comparison.
Average caseO(log n)Each comparison halves the remaining window.
Worst caseO(log n)The window shrinks to a single element before a match or a miss.
SpaceO(1)Iterative version keeps only the lo, hi and mid indices.

Step by step

StepWhat happens
1Set lo to the first index and hi to the last index of the sorted array.
2Compute the middle index: mid = (lo + hi) // 2.
3If a[mid] equals the target, return mid (found).
4If a[mid] is **less** than the target, the target can only be in the right half: set lo = mid + 1.
5If a[mid] is **greater** than the target, search the left half: set hi = mid - 1.
6Repeat from step 2 while lo <= hi; if the window empties, the target is not in the array.

Worked example

Searching for 5 in [1, 2, 3, 5, 7, 8, 9]:

PassWindow (lo..hi)mida[mid]Action
1[1, 2, 3, 5, 7, 8, 9] (0..6)35a[3] = 5: target found at index 3.

A miss, step by step

Searching for 4 in the same array shows how the window empties:

PassWindow (lo..hi)mida[mid]Action
10..6355 > 4: search the left half, hi = 2.
20..2122 < 4: search the right half, lo = 2.
32..2233 < 4, so lo becomes 3 and the window empties: not found.

When to use binary search

Use it whenAvoid it when
The data is already sorted (or you search it many times)The data is unsorted and searched only once (sorting first costs O(n log n))
The collection supports fast random access (arrays)You only have sequential access (linked lists)
The dataset is large (O(log n) shines at scale)The dataset is tiny (a simple scan is just as fast and simpler)

Binary Search code

A clean, runnable Binary Search implementation in Python, JavaScript, Java, C++, C, Pseudocode. Pick a language, copy the code, or open it pre-loaded in the 365education compiler’s Playground.

 

Binary Search code in C++ JavaScript Java C & Pseudocode
C++ 
def binary_search(a, target):

    lo = 0
    hi = len(a) - 1

    while lo <= hi:

        mid = lo + (hi - lo) // 2

        if a[mid] == target:
            return mid

        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1


nums = [
    1, 2, 3, 5, 7, 8, 9
]


print(
    "Index of 5:",
    binary_search(nums, 5)
)


print(
    "Index of 4:",
    binary_search(nums, 4)
)
function binarySearch(a, target) {

    let lo = 0;
    let hi = a.length - 1;

    while (lo <= hi) {

        const mid =
            lo + Math.floor(
                (hi - lo) / 2
            );

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

        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}


const nums = [
    1, 2, 3, 5, 7, 8, 9
];


console.log(
    "Index of 5:",
    binarySearch(nums, 5)
);


console.log(
    "Index of 4:",
    binarySearch(nums, 4)
);
public class Main {

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

        int lo = 0;
        int hi = a.length - 1;

        while (lo <= hi) {

            int mid =
                lo + (hi - lo) / 2;

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

            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return -1;
    }


    public static void main(
        String[] args
    ) {

        int[] nums = {
            1, 2, 3, 5, 7, 8, 9
        };


        System.out.println(
            "Index of 5: "
            + binarySearch(
                nums,
                5
            )
        );


        System.out.println(
            "Index of 4: "
            + binarySearch(
                nums,
                4
            )
        );

    }
}
#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& a, int target) {
    int lo = 0;
    int hi = static_cast<int>(a.size()) - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (a[mid] == target)
            return mid;

        if (a[mid] < target) {
            lo = mid + 1; // search the right half
        } else {
            hi = mid - 1; // search the left half
        }
    }

    return -1;
}

int main() {

    std::vector<int> nums = {
        1, 2, 3, 5, 7, 8, 9
    };

    // must be sorted

    std::cout
        << "Index of 5: "
        << binarySearch(nums, 5)
        << "\n";

    std::cout
        << "Index of 4: "
        << binarySearch(nums, 4)
        << "\n";

    return 0;
}
#include <stdio.h>

int binarySearch(
    int a[],
    int size,
    int target
) {

    int lo = 0;
    int hi = size - 1;

    while (lo <= hi) {

        int mid =
            lo + (hi - lo) / 2;

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

        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}


int main() {

    int nums[] = {
        1, 2, 3, 5, 7, 8, 9
    };

    int size = 7;


    printf(
        "Index of 5: %d\n",
        binarySearch(
            nums,
            size,
            5
        )
    );


    printf(
        "Index of 4: %d\n",
        binarySearch(
            nums,
            size,
            4
        )
    );


    return 0;
}
FUNCTION BinarySearch(A, Target)

    Low ← 0
    High ← LENGTH(A) - 1

    WHILE Low ≤ High

        Mid ← Low + (High - Low) DIV 2

        IF A[Mid] = Target THEN
            RETURN Mid
        ENDIF

        IF A[Mid] < Target THEN
            Low ← Mid + 1
        ELSE
            High ← Mid - 1
        ENDIF

    ENDWHILE

    RETURN -1

ENDFUNCTION


Numbers ← [1, 2, 3, 5, 7, 8, 9]


OUTPUT BinarySearch(
    Numbers,
    5
)


OUTPUT BinarySearch(
    Numbers,
    4
)
Binary Search searches a sorted array by repeatedly dividing the search range in half.
Time complexity: O(log n)   |  Space complexity: O(1)

Powered by