Binary Search

In the previous lesson, we learned Linear Search, where elements are checked one by one.

While Linear Search is simple, it becomes slow when the dataset grows large.

In this lesson, we introduce a much faster searching technique — Binary Search.

The Key Requirement for Binary Search

Binary Search works only on sorted data.

This is the most important rule to remember. If the data is not sorted, Binary Search will not work correctly.

Sorting enables us to eliminate half of the data in every step.

Binary Search – Core Idea

Binary Search follows a divide-and-conquer approach.

Instead of checking elements one by one, it repeatedly:

• Finds the middle element
• Compares it with the target
• Discards half of the search space

This drastically reduces the number of comparisons.

How Binary Search Works (Step-by-Step)

Consider the sorted list:

[10, 20, 30, 40, 50, 60]

Target value: 40

Step-by-step process:

• Middle element = 30 → target is larger
• Search right half → [40, 50, 60]
• Middle element = 50 → target is smaller
• Search left half → [40]
• Element found

The search finishes in very few steps.

Binary Search Algorithm (Code)

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

numbers = [10, 20, 30, 40, 50, 60]
result = binary_search(numbers, 40)

if result != -1:
    print("Element found at index", result)
else:
    print("Element not found")

The algorithm repeatedly narrows the search range until the element is found or the range becomes empty.

Time Complexity of Binary Search

Binary Search reduces the search space by half in every iteration.

Time complexity:

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

This makes Binary Search much faster than Linear Search for large datasets.

Why Binary Search Is So Efficient

Every comparison eliminates half of the remaining elements.

For example:

• 1,000,000 elements → ~20 comparisons
• 1,000 elements → ~10 comparisons

This efficiency is the reason Binary Search is widely used in systems, databases, and libraries.

Real-World Example

Think about searching for a word in a dictionary.

You do not start from page one. Instead, you open near the middle, check the word, and jump left or right.

That is Binary Search in action.

Limitations of Binary Search

Binary Search has important limitations:

• Data must be sorted
• Sorting itself takes time
• Not suitable for frequently changing data

Because of this, Binary Search is best used when searching many times on static data.

Mini Practice

Think carefully:

• Would Binary Search work on an unsorted array?
• Is sorting worth it for a single search?

Exercises

Quick Quiz

In the next lesson, we will formally analyze searching performance and understand the Divide and Conquer strategy that powers many efficient algorithms.