Description
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 l=0 and the right boundary r=n-1 for binary search.
In each iteration, we calculate the middle position mid=(l+r)/2, then compare the size of nums[mid] and target.
- If nums[mid] ≥ target, it means target is in the left half, so we move the right boundary r to mid;
- Otherwise, it means target is in the right half, so we move the left boundary l to mid+1.
The loop ends when l<r, at this point nums[l] is the target value we are looking for. If nums[l]=target, return l; otherwise, return -1.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l if nums[l] == target else -1(code-box)
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l] == target ? l : -1;
}
}(code-box)
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l] == target ? l : -1;
}
};(code-box)
func search(nums []int, target int) int {
l, r := 0, len(nums)-1
for l < r {
mid := (l + r) >> 1
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
if nums[l] == target {
return l
}
return -1
}(code-box)
function search(nums: number[], target: number): number {
let [l, r] = [0, nums.length - 1];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l] === target ? l : -1;
}(code-box)
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let mut l: usize = 0;
let mut r: usize = nums.len() - 1;
while l < r {
let mid = (l + r) >> 1;
if nums[mid] >= target {
r = mid;
} else {
l = mid + 1;
}
}
if nums[l] == target {
l as i32
} else {
-1
}
}
}(code-box)
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
let [l, r] = [0, nums.length - 1];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l] === target ? l : -1;
};(code-box)
public class Solution {
public int Search(int[] nums, int target) {
int l = 0, r = nums.Length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l] == target ? l : -1;
}
}(code-box)
