Binary Search Technique

What is the Binary Search Technique?

The Binary Search technique is used to find the position of a target element in a sorted list or array. Instead of checking every element one by one (as in linear search), binary search efficiently cuts the search space in half at every step.

This makes it significantly faster with a time complexity of O(log n) compared to O(n) for linear search.

How Does Binary Search Work?

Binary search works by repeatedly dividing the search interval in half:

1. Start with the full array range: low = 0 and high = n - 1.
2. Find the middle index: mid = (low + high) // 2.
3. If arr[mid] equals the target, return mid.
4. If arr[mid] is greater than the target, search in the left half.
5. If arr[mid] is less than the target, search in the right half.
6. Repeat until the range becomes invalid (low > high).

Pseudocode

// Binary Search Pseudocode
function binarySearch(arr, target):
    low = 0
    high = arr.length - 1

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

        if arr[mid] == target:
            return mid  // Found
        else if arr[mid] < target:
            low = mid + 1  // Search right half
        else:
            high = mid - 1  // Search left half

    return -1  // Not found

Dry Run Example

Problem Description:

You are given a sorted array:

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

Your task is to find the index of the number 60 using the Binary Search technique.

Our Approach (For Beginners)

• Start with the entire array and define two pointers: low = 0 and high = length - 1.
• Find the middle index: mid = (low + high) // 2.
• Check the value at arr[mid]:
• If it's the target → return index.
• If it's less than the target → search in right half.
• If it's more than the target → search in left half.
• Repeat until the target is found or the search space becomes invalid.

Step-by-Step Dry Run

Step	low	high	mid	arr[mid]	Action
1	0	7	(0+7)//2 = 3	40	40 < 60 → search in right half
2	4	7	(4+7)//2 = 5	60	Found target at index 5

Final Result:

Target 60 found at index 5.

Why is this Efficient?

• We didn't check each element.
• With just 2 steps, we found the number!
• Binary Search reduces the search range by half at every step — that’s why it's so fast!

Time Complexity:

O(log n) – because we halve the search space each time.

Space Complexity:

O(1) – we use only a few variables regardless of input size, and these are going to be constant irrespective of the array size.

Examples of Binary Search Applications

• Finding an element in a sorted array.
• Finding the first/last occurrence of a number in a sorted array.
• Lower bound / Upper bound problems.
• Peak element in a mountain array.
• Solving problems using binary search on answer space (like "Koko Eating Bananas").

Variants of Binary Search

• Lower Bound: Find the first index where element ≥ target.
• Upper Bound: Find the first index where element > target.
• Binary Search on Answers: Use binary search on a range of potential answers, not just an array (e.g., min/max capacity, speed, distance).

Time and Space Complexity

• Time Complexity: O(log n)
• Space Complexity: O(1) for iterative version, O(log n) for recursive version (due to call stack)

Advantages of Binary Search

• Extremely Efficient: Handles large datasets quickly.
• Logarithmic Time: Grows slowly with input size.
• Simple and Powerful: Easily adapted to a variety of search problems.

Disadvantages

• Requires sorted data.
• May be trickier to implement with boundaries and conditions (prone to off-by-one errors).

Conclusion

Binary Search is one of the most powerful and widely-used techniques in DSA. It's not just used for finding elements in arrays, but also as a strategic tool to reduce time complexity in problems involving ranges, monotonic functions, and optimization tasks.