二分查找要求数据有二段性，可以将查找某个分割点的时间复杂度从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这个条件，答案蕴藏在其中！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
}