Binary Search - Video Solutions

Problem Overview: Given a sorted integer array nums and a target, return the index of the target if it exists. If the value is not present, return -1. The key constraint is that the array is already sorted, which allows you to use binary search instead of scanning every element.

Approach 1: Linear Scan (Brute Force) (Time: O(n), Space: O(1))

The most direct approach is to iterate through the array from left to right and compare every element with target. The moment you find a match, return its index. If the loop finishes without finding the value, return -1. This works for any array, sorted or not, but it ignores the sorted property entirely. Each lookup may require scanning the entire array, so the time complexity grows linearly with n.

Approach 2: Iterative Binary Search (Time: O(log n), Space: O(1))

Binary search cuts the search space in half on every step. Start with two pointers: left = 0 and right = n - 1. Compute the middle index using mid = left + (right - left) / 2 to avoid overflow. If nums[mid] == target, return mid. If the middle value is smaller than the target, discard the left half by setting left = mid + 1. Otherwise discard the right half with right = mid - 1. Continue until the pointers cross. Because the search space halves each iteration, the time complexity is O(log n) and the algorithm uses O(1) extra space.

This iterative form is the most common implementation in production code. It avoids recursion overhead and keeps memory usage constant. Many interviewers prefer this version because it shows clear pointer control and correct boundary handling.

Approach 3: Recursive Binary Search (Time: O(log n), Space: O(log n))

The same halving logic can be expressed recursively. Define a function that takes left and right boundaries. Compute mid, compare with the target, and recursively search either the left or right half. The recursion stops when left > right. Each recursive call reduces the problem size by half, so the time complexity remains O(log n). However, recursion adds call stack overhead, giving it O(log n) auxiliary space.

This version is easier to reason about conceptually because the code mirrors the divide-and-conquer idea directly. It is also a good demonstration of recursion, though most engineers switch to the iterative version in performance-sensitive code.

Recommended for interviews: Iterative binary search is the expected solution. It demonstrates that you recognize the sorted array property and can reduce the search space efficiently to O(log n). Mentioning the linear scan shows baseline understanding, but implementing binary search correctly—especially pointer updates and midpoint calculation—demonstrates real algorithmic skill.