Loading problems...
TL;DR: The optimal solution leverages the sorted property of the array to repeatedly halve the search space by comparing the middle element to the target, achieving logarithmic time complexity.
The problem asks us to determine the index of a specific integer target within a sorted array of unique integers called nums. If the target is present, we return its index; otherwise, we return -1. This is the canonical definition of the LeetCode 704 problem, serving as the foundational example for the Binary Search algorithm. The constraints explicitly mandate an algorithm with O(log n) runtime complexity, ruling out linear scanning methods.
The most intuitive way to search for an element in an array is to check every single element one by one. This is known as a linear search.
Pseudo-code:
text
function bruteForce(nums, target):
for index from 0 to length of nums - 1:
if nums[index] equals target:
return index
return -1Time Complexity Analysis:
The time complexity of this approach is O(n), where n is the number of elements in nums. In the worst-case scenario (target is at the end or not present), the algorithm must visit every element.
Why it fails:
While this approach yields the correct result, the problem description explicitly requires an O(log n) runtime complexity. An O(n) solution is exponentially slower than O(log n) for large inputs. In a rigorous interview setting or against strict time limits, the brute force approach is considered incorrect because it fails to utilize the critical property that nums is sorted.
The key intuition behind the optimal solution lies in the sorted order of the input array. In an unsorted array, checking an element at index i gives us no information about the location of the target relative to i—the target could be anywhere. However, in a sorted array, comparing the target to a value at the middle index mid provides significant information:
nums[mid] == target, we have found the element.nums[mid] > target, because the array is sorted ascendingly, all elements to the right of mid (indices mid + 1 to n - 1) must also be greater than target. Therefore, the target effectively cannot exist in the right half. We can discard that entire section.nums[mid] < target, all elements to the left of mid are smaller than target. The target cannot exist in the left half, and we can discard it.This logic allows us to reduce the search space by half in every iteration.
Visual Description:
Imagine the search space defined by two pointers, left and right. Initially, they encompass the entire array. We calculate the mid point. If the value at mid is not the target, one of the pointers moves past mid, effectively "closing" the window on the half of the array that cannot contain the target. This window shrinks exponentially until the target is found or the pointers cross, indicating the search space is empty.

Let's trace the algorithm with nums = [-1, 0, 3, 5, 9, 12] and target = 9.
left = 0, right = 5. Search space is indices [0, 5].left <= right (0 <= 5) is true.mid: 0 + (5 - 0) / 2 = 2.nums[2] is 3.3 with target (9). Since 3 < 9, target is in the right half.left to mid + 1 = 3.[3, 5].left <= right (3 <= 5) is true.mid: 3 + (5 - 3) / 2 = 4.nums[4] is 9.9 with target (9). They are equal.4.The correctness of this algorithm relies on the invariant that if the target exists in the array, it must be located within the current interval [left, right].
[0, n-1]. If the target exists, it is trivially within this range.target with nums[mid].
nums[mid] < target, then for all i <= mid, nums[i] < target (due to sorting). Thus, the target cannot be in [left, mid]. By setting left = mid + 1, we preserve the invariant that the target is in the new range [mid + 1, right].nums[mid] > target, then for all i >= mid, nums[i] > target. The target cannot be in [mid, right]. By setting right = mid - 1, we preserve the invariant for the new range [left, mid - 1].left > right. This implies the search interval is empty. Since the invariant guarantees the target would be in the interval if it existed, an empty interval proves the target is not present in the array.cppclass Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { // Prevent potential integer overflow int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { // Target is in the right half left = mid + 1; } else { // Target is in the left half right = mid - 1; } } return -1; } };
javaclass Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { // Calculate mid to avoid overflow int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { // Target is in the upper half left = mid + 1; } else { // Target is in the lower half right = mid - 1; } } return -1; } }
pythonclass Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 while left <= right: # Integer division in Python mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: # Target must be to the right left = mid + 1 else: # Target must be to the left right = mid - 1 return -1
Time Complexity: O(log n)
In each iteration of the loop, the size of the search space right - left is reduced by approximately half. If the array has n elements, the maximum number of iterations required to reduce the search space to size 1 is log₂ n. Therefore, the time complexity is logarithmic.
Space Complexity: O(1)
The algorithm operates in constant space. We only store a few integer variables (left, right, mid) regardless of the size of the input array.
The Binary Search - On Sorted Array/List pattern is highly versatile. Understanding the logic in LeetCode 704 allows you to solve several related problems:
-1 when the target isn't found, you return left, which represents the index where the target should be inserted to maintain order.Why do I get a "Time Limit Exceeded" error?
left = mid or right = mid without the +1 or -1 offset.mid might result in mid equaling left. If you set left = mid in the else block, the pointers never change, creating an infinite loop.mid + 1 or to strictly reduce the search space.mid - 1Why does my code fail on single-element arrays?
while (left < right) instead of while (left <= right).left == right, the search interval contains exactly one element. If the condition is strict inequality (<), the loop terminates before checking this final element.-1 incorrectly.Why is (left + right) / 2 considered risky?
(left + right) / 2 in languages with fixed-size integers (like C++ or Java).left and right are both large positive integers (near INT_MAX), their sum can overflow into a negative number before division.nums[mid] with a negative index will cause a runtime error (Index Out of Bounds) or undefined behavior. Use left + (right - left) / 2.