704. Binary Search
EasyTopics
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
C++Auto
1 class Solution {
2 public:
3 int solve(vector<int>& nums) {
4 // Your code here
5
6 }
7 };
Interview CrackedREADY
Thinking Process: O(log n) analysis...Model: GPT
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
};
Time: O(log n)Space: O(1)