二分查找要求数据有二段性,可以将查找某个分割点的时间复杂度从O(N)加速至O(logN)

LC704. 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target

写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出:4
解释:9出现在 nums中并且下标为4
示例2:
输入:nums = [-1,0,3,5,9,12],target = 2 输出:-1
解释:2不存在nums中因此返回-1

思路:

二分查找->梦开始的地方

这道题是二分查找的入门题目,二分查找的水非常深,但是简单的题目通常会由于各种原因丢分。

这里我总结一下二分查找的一些模板和做题套路

首先能用二分查找的前提是在可以根据f(mid)的值来判断下一个合法区间在mid左边还是右边

因此二分查找前面通常都会有排序等步骤来确保问题具有**“二段性”**

总体要注意的:

1.while (l < r): 这种写法使得退出条件是l==r,因此执行完之后必定有l==r

2.mid的求法: 这个mid的求法非常讲究,我总结的是

  • mid = l + (r - l + 1) / 2,mid主动偏右->右边界主动收缩r = mid - 1;
  • mid = l + (r - l ) / 2,mid主动偏左->左边界主动收缩l = mid + 1;

3.下一个区间的判断采用减治思想,将一定不符合条件的先排除,如:nums[mid] > target,那么mid必定不符合题意!->r = mid - 1

然后另外一个区间是其反面,一般是将合法区间包含在边界,如:nums[mid] <=target,那么mid可能不符合题意!->l = mid

4.退出循环的时候要重复利用好l==r这个条件,答案蕴藏在其中!

class Solution {
public int search(int[] nums, int target) {
/*
在升序数组中查找目标数字对应下标->二分查找
*/
int l = 0, r = nums.length - 1;
while (l < r) {
// 下面是右边主动收缩
int mid = l + (r - l + 1) / 2;
// >target,说明target在左边(不含)
if (nums[mid] > target) {
r = mid - 1;
} else {
// <=target,说明target在右边(含)
l = mid;
}
}
// l==r,nums[l]要不就是target;要不就是nums中没有target
return nums[l] == target ? l : -1;
}
}