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 < 104
All the integers in nums are unique.
nums is sorted in ascending order.
Solutions
Solution 1: Binary Search
We define the left boundary of the binary search as $left=0$, and the right boundary as $right=n-1$.
In each iteration, we calculate the middle position $mid=(left+right)/2$, and then compare the size of $nums[mid]$ and $target$:
If $nums[mid] \geq target$, it means that $target$ is in the interval $[left, mid]$, so we update $right$ to $mid$;
Otherwise, $target$ is in the interval $[mid+1, right]$, so we update $left$ to $mid+1$.
When $left \geq right$, we check if $nums[left]$ equals $target$. If it does, we return $left$, otherwise, we return $-1$.
The time complexity is $O(\log n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.