# 二分查找
# 题目描述
在一个排序数组中,快速查找指定元素,返回该下标,如果没有,则返回 -1
。
二分查找,有很多变种题,例如找第一个大于等于指定数的下标,最后一个大于等于指定数,第一个小于等于指定数的下标,最后小于等于指定数的下标等等。但万变不离其宗都是关键词
排序
与二分查找
。
# 关键词
排序 二分查找 折半查找# 思路
- 数组已经排好序,一般是基础条件。
- 设置两个指针
left
,right
,分别指向头部和尾部。 - 每次算当前查找范围的中间下标
middle = Math.floor(right - left) / 2
,判断target
与nums[middle]
的值大小。 - 比
nums[middle]
大,则接下来查找范围改为[middle + 1, right]
。 - 比
nums[middle]
小,则接下来查找范围改为[left, middle - 1]
。 - 与
nums[middle]
相等,则返回middle
。 - 遍历完了,都没有,则返回
-1
。
一图胜千言
![binary_search](/binary_search.gif)
# 代码
const binarySearch = function(nums, target) {
const n = nums.length;
let left = 0;
let right = n - 1;
while (left <= right) {
let middle = Math.floor((right - left)) + left;
if (nums[middle] > target) {
right = middle - 1;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
# 复杂度分析
- 时间复杂度:O(logN)
- 空间复杂度:O(1)