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, 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 at index 4.
Example 2
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 not in nums.
1 <= nums.length <= 10^4All integers in nums are unique.-10^4 < nums[i], target < 10^4The brute-force answer — scan every element left to right — works and is O(n), but the array being SORTED is a strong hint that a smarter approach exists.
Sorted order means one comparison at the midpoint eliminates HALF the remaining search space — you never need to look at the eliminated half at all.
Use left + (right - left) / 2 rather than (left + right) / 2 to compute the midpoint — the latter can silently overflow for very large index values.
public int searchBruteForce(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) return i;
}
return -1;
}Time: O(n) · Space: O(1)