704. Binary Search
Problem
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:
Example 2:
Constraints:
- 1 <= nums.length <= 104
- -104 < nums[i], target < 104
- All the integers in nums are unique.
- nums is sorted in ascending order.
Approach
This is a very simple algorithm that everyone should know.
The idea is that, since the values are sorted, we can throw away half off the values on each iteration. We start by initializing two pointers, one on each side. On each iteration, we check the midpoint value of the two pointers. If the mid point equals the target, we return the value. If it doesn't that means it's either on the left side or the right side depending on if the middle value is larger or greater than the target. If the middle value is larger than the target, that means the value is on the left side (smaller side) of the array. So, we can set our right pointer to one less than the middle. If the middle value is smaller than the target, that means the value is on the right side (larger side) of the array. So, we can set our left pointer to one more than the middle. If we complete the iterations, that means the value is not in the array.
Complexity
Time: O(log n)
Since we're halving the array on each iteration, this is a log based 2 algorithm.
Space: O(1)
No extra space is created.