Binary Search is one of the most fundamental algorithms every programmer should know. It’s fast, elegant, and appears frequently in coding interviews.

In this post, we’ll break down the problem, understand the intuition behind Binary Search, and walk through a clean Python implementation.

Problem Statement

Given a sorted array of distinct integers nums and an integer target, return the index of target if it exists. Otherwise, return -1.

The catch is that the solution must run in O(log n) time, which immediately hints that Binary Search is the right approach.

Example 1

Input:
nums = [-1, 0, 2, 4, 6, 8]
target = 4

Output:
3

Example 2

Input:
nums = [-1, 0, 2, 4, 6, 8]
target = 3

Output:
-1

Why Binary Search?

A linear search checks every element one by one, taking O(n) time.

Since the array is already sorted, we can do much better by repeatedly cutting the search space in half.

Think of it like searching for a word in a dictionary:

  • Open the dictionary near the middle.
  • If your word comes before that page, search the left half.
  • If it comes after, search the right half.
  • Repeat until you find the word or there are no pages left.

Every comparison eliminates half of the remaining elements, giving us a time complexity of O(log n).

The Algorithm

We maintain two pointers:

  • l → left boundary
  • r → right boundary

While the search space is valid (l <= r):

  1. Find the middle index.
  2. Compare the middle element with the target.
  3. If the middle value is too large, discard the right half.
  4. If it’s too small, discard the left half.
  5. If it matches, return the index.

If the loop finishes without finding the target, return -1.

Python Solution

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            mid = l + (r - l) // 2

            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid

        return -1

Dry Run

Let’s search for target = 6.

nums = [-1, 0, 2, 4, 6, 8]

l = 0
r = 5

First iteration

mid = 2
nums[mid] = 2

Since 2 < 6, the target must be on the right.

l = mid + 1 = 3

Second iteration

l = 3
r = 5

mid = 4
nums[mid] = 6

We found the target!

Return 4

Why Calculate Mid Like This?

You’ll often see:

mid = l + (r - l) // 2

instead of

mid = (l + r) // 2

Both work in Python because integers don’t overflow. However, the first version is considered best practice since it avoids integer overflow in languages like Java and C++ where l + r could exceed the maximum integer value.

Using this formula makes your solution portable across programming languages.

Complexity Analysis

Time Complexity: O(log n)

  • Each iteration halves the search space.

Space Complexity: O(1)

  • Only a few variables are used regardless of the input size.

Key Takeaways

  • Binary Search only works on sorted data.
  • Use two pointers (l and r) to define the current search space.
  • Compare the middle element and eliminate half of the array each iteration.
  • The algorithm runs in O(log n) time and O(1) space, making it one of the most efficient search algorithms for sorted arrays.

Mastering Binary Search is essential because many interview problems are variations of this same pattern. Once you’re comfortable with the basic implementation, you’ll be ready to tackle more advanced problems involving rotated arrays, search boundaries, and answer-space binary search.