Binary Search

TL;DR Binary Search is a divide-and-conquer algorithm that efficiently finds a target in a sorted array by repeatedly halving the search space. It compares the middle element and eliminates half of the remaining elements each time.

1. Algorithm Steps

1. Start with two pointers: left = 0, right = len(array) - 1.

2. While left <= right:

• Compute middle = (left + right) // 2.

• If array[middle] == target, return middle.

• If array[middle] < target, move left = middle + 1.

• If array[middle] > target, move right = middle - 1.

3. If the target is not found, return -1.

The recursive version follows the same logic but uses function calls to handle the bounds.

2. Complexity

| Case | Time | Space | Notes |

| ------------- | ----------- | --------- | ------------------------------ |

| Best | O(1) | O(1) | Target is at the middle |

| Average | O(log n)| O(1) (iterative) / O(log n) (recursive) | Dividing array each step |

| Worst | O(log n)| O(1) / O(log n) | Target not found or last match |

| Stability | ❌ Not Stable | – | Doesn’t preserve order |

3. Optimizations & Variants

• Recursive vs Iterative: Recursive is cleaner, iterative is more memory-efficient.

• Lower/Upper Bound Search: Modify to find the first or last occurrence.

• Binary Search on Answer: Used in problems where the search space is implicit (e.g., finding minimum time, max capacity).

• Rotated Array Search: Requires extra conditions to handle pivoted array.

4. Reference Python Implementation

Recursive version:

def binarySearch(array, target):

return binarySearchHelper(array, target, 0, len(array) - 1)

  

def binarySearchHelper(array, target, left, right):

if left > right:

return -1

middle = (left + right) // 2

if array[middle] == target:

return middle

elif array[middle] < target:

return binarySearchHelper(array, target, middle + 1, right)

else:

return binarySearchHelper(array, target, left, middle - 1)

5. Practice

Prompt: Implement binary search on a sorted list of integers.

Sample Input:

array = [0, 1, 21, 33, 45, 45, 61, 71, 72, 73]

target = 33

Expected Output: 3

Time & Space Complexity:

• Time: O(log n)

• Space: O(1) for iterative, O(log n) for recursive

6. When (Not) to Use Binary Search

• ✅ Use when array is sorted.

• ✅ Use when you need to quickly locate elements in large datasets.

• ❌ Don’t use on unsorted arrays or linked lists (random access is required).

7. Quick Self-Check

1. What is the time complexity of Binary Search?

2. Can Binary Search work on unsorted data?

3. What’s the difference in space complexity between recursive and iterative implementations?

4. What happens if the element appears multiple times?

8. Further Reading

• Introduction to Algorithms (CLRS), Chapter on Searching

• Visualgo – Binary Search

• CP-Algorithms: Binary Search

Stay sharp, divide smart! 🧠🔍