Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104-104 < nums[i], target < 104nums are unique.nums is sorted in ascending order.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.
The iterative binary search approach involves using a loop to divide the array into halves repeatedly until the target is found or the search range is empty. This approach utilizes two pointers, 'low' and 'high', that represent the current search bounds.
This C code implements an iterative binary search. It uses a loop to adjust the low and high pointers based on comparisons, eventually finding the target or concluding it is not present.
Time Complexity: O(log n), as we divide the search space in half each time.
Space Complexity: O(1), only a constant amount of space is used.
The recursive binary search involves calling a function that repeatedly calls itself with updated bounds until the target is found or the bounds overlap. This approach provides a cleaner implementation at the cost of additional space used by the call stack.
This C solution uses recursion to split the problem into smaller subproblems, updating 'low' and 'high' in each recursive call.
Time Complexity: O(log n)
Space Complexity: O(log n) due to the stack space used by recursion.
We define the left boundary l=0 and the right boundary r=n-1 for binary search.
In each iteration, we calculate the middle position mid=(l+r)/2, then compare the size of nums[mid] and target.
nums[mid] geq target, it means target is in the left half, so we move the right boundary r to mid;target is in the right half, so we move the left boundary l to mid+1.The loop ends when l<r, at this point nums[l] is the target value we are looking for. If nums[l]=target, return l; otherwise, return -1.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Iterative Binary Search | Time Complexity: O(log n), as we divide the search space in half each time. |
| Recursive Binary Search | Time Complexity: O(log n) |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | When the array is unsorted or simplicity matters more than performance |
| Iterative Binary Search | O(log n) | O(1) | Best choice for sorted arrays and interview solutions |
| Recursive Binary Search | O(log n) | O(log n) | When demonstrating divide-and-conquer or recursion patterns |
Binary Search - Leetcode 704 - Python • NeetCode • 254,182 views views
Watch 9 more video solutions →Practice Binary Search with our built-in code editor and test cases.
Practice on FleetCode