The Problem
Given a sorted array of integers nums and a target 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.
The Core Concept: Divide & Conquer
Binary Search operates on a simple principle: since the array is already sorted, we can query the middle element.
- If the middle element matches our target, we are done!
- If the target is smaller than the middle element, the target must reside in the left half. We can discard the entire right half.
- If the target is larger than the middle element, the target must reside in the right half. We can discard the entire left half.
By halving our search space at each iteration, we locate the element in logarithmic time.
Code Implementation
Here is the standard iterative version of Binary Search:
- Time Complexity: O(log N) as we halve the array size each step.
- Space Complexity: O(1) auxiliary space for pointers.
Interactive Lab: Binary Search
Try setting custom values, modifying the search target, and stepping through the execution to watch pointers (low, high, mid) shift in real-time.
Key Takeaway
Binary Search is extremely powerful. For a list of 4 billion items, it takes at most 32 operations to locate any item or determine its absence. The primary requirement is that the collection must be sorted.