704. 二分查找
704. 二分查找
题目
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 <= 10^4
-104 < nums[i], target < 10^4
- All the integers in
nums
are unique. nums
is sorted in ascending order.
题目大意
给定一个 n
个元素有序的(升序)整型数组 nums
和一个目标值 target
,写一个函数搜索 nums
中的 target
,如果目标值存在返回下标,否则返回 -1
。
解题思路
这是一道典型的查找问题,nums
是有序的(升序)整型数组,因此可以利用二分查找的思想高效解决,目标是找到nums
中值等于 target
的下标,如果不存在则返回 -1
。
- 初始化左右指针:
- 左指针
left = 0
,右指针right = nums.length - 1
。
- 左指针
- 二分查找:
- 计算中间点
mid = (left + right) / 2 | 0
。 - 如果
nums[mid] == target
,直接返回mid
。 - 如果
nums[mid] > target
,更新右边界为mid - 1
。 - 如果
nums[mid] < target
,更新左边界为mid + 1
。
- 计算中间点
- 结束条件:
- 当
left > right
时,仍没有找到符合的目标值,返回-1
。
- 当
复杂度分析
- 时间复杂度:
O(log n)
,其中n
是数组的长度,二分查找的时间复杂度为O(log n)
。 - 空间复杂度:
O(1)
,仅使用了常数空间。
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((right + left) / 2);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return -1;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
702 | 搜索长度未知的有序数组 🔒 | 数组 二分查找 交互 | 🟠 | 🀄️ 🔗 | |
2529 | 正整数和负整数的最大计数 | 数组 二分查找 计数 | 🟢 | 🀄️ 🔗 |