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

LC704. 二分查找 {#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; } } |