Let’s go deep into Binary Search so that you don’t just “know the code“, you understand exactly why every line exists and what’s happening in your brain when you run it.

The Big Idea

Binary search is a divide and conquer algorithm for searching in a sorted list.

• If the list is not sorted, binary search won’t work (we’ll see why).

• It repeatedly splits the search space in half until it finds the element or runs out of places to look.

Think of it like:

You’re looking for a word in a dictionary. You don’t flip one page at a time; you open near the middle, check, then decide which half to keep.

Why Sorted?

Let’s say you’re looking for 45 in:

[10, 15, 20, 25, 30, 35, 40, 45, 50, 55]

If it’s sorted:

• You can check the middle and decide whether to go left or right because you know all left elements are smaller, all right elements are bigger.

• This “direction“ is possible only if the list is sorted.

If the list is unsorted:

[45, 10, 55, 30, 20]

Checking the middle tells you nothing — you’d have to search linearly.

The Steps (Logic)

Let’s write it in human language first:

1. Start with the entire range:

   low = 0, high = len(list) - 1

2. While there’s still a range left (low <= high):

   • Find the middle index:

     mid = (low + high) // 2

     (integer division so we don’t get fractions)

   • If arr[mid] == target: 🎯 Found it! Return the index.

   • If arr[mid] < target:

     → Target is in the right half. Move low to mid + 1.

   • If arr[mid] > target:

     → Target is in the left half. Move high to mid - 1.

3. If loop ends → Target not found, return something like -1.

The “Why“ of mid = (low + high) // 2

We take the middle to cut the search space in half each time:

• If you start with 1,000,000 items:

  • 1st step: check middle → ~500,000 left to search.

  • 2nd step: ~250,000 left.

  • 3rd: ~125,000.

  • And so on…

    This is why binary search is O(log n) in time complexity.

Python Code (Iterative Version)

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

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

        if arr[mid] == target:
            return mid  # Found at index mid

        elif arr[mid] < target:
            low = mid + 1  # Search right half

        else:
            high = mid - 1 # Search left half

    return -1  # Not found

Python Code (Recursive Version)

For completeness — recursion just means “function calling itself on the smaller half“.

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1 # Not found

    mid = (low + high) // 2

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

Call it like:

arr = [10, 15, 20, 25, 30, 35, 40, 45, 50, 55]
print(binary_search_recursive(arr, 45, 0, len(arr) - 1))

Complexity

• Time Complexity:

  • Best case: O(1) (found at first try)

  • Worst/Average case: O(log n)

• Space Complexity:

  • Iterative: O(1)

  • Recursive: O(log n) (stack frames for recursion)

Common Pitfalls

• Forgetting to sort the list first.

• Infinite loops when low or high doesn’t move properly.

• Off-by-one errors in the index calculations.

• Integer overflow for mid = (low + high) // 2 in some languages — Python is safe because integers are big, but in C/C++ we often use mid = low + (high - low) // 2.