Binary Search
Description: Given a sorted ascending array nums and a number target, return the index of target if it exists, otherwise return -1.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 is at index 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 is not present
Constraints:
1 <= nums.length <= 10⁴
Массив отсортирован по возрастанию
Все значения уникальны
Recommended time and space complexity
Aim for O(log n) time and O(1) space.
Hint 1
Linear search gives O(n). The array is sorted — use that.
Hint 2
Compare the middle with the target: if smaller, go right, else go left.
Hint 3
Watch the boundaries: loop while left <= right.