Given a sorted array of integers `nums` and a target value, return the index of the target if found. If not found, return -1. You must write an algorithm with O(log n) runtime complexity.
Examples
Example 1 Input:nums = [-1,0,3,5,9,12], target = 9
Output:4
Example 2 Input:nums = [-1,0,3,5,9,12], target = 2
Output:-1
Constraints
▪1 <= nums.length <= 10^4
▪All elements are unique.
▪nums is sorted in ascending order.
Hints
Hint 1Show
Use two pointers: left and right.
Hint 2Show
Find the middle element and compare with target.
Hint 3Show
If middle < target, search right half. If middle > target, search left half.
Starter Code
Solution.cpp
1class Solution {
2public:
3 int search(std::vector<int>& nums, int target) {
4 // Your code here
5 return -1;
6 }
7};
Solution
Solve the problem first before reviewing the solution!