一.二分查找基础
1、二分查找介绍
二分查找(Binary search)也称折半查找，是一种效率较高的查找方法，时间复杂度。当对查数题目有时间复杂度要求是，首先就要考虑到二分查找。二分查找的思想很简单，属于分治策略的变种情况。但是，二分查找要求线性表中的记录必须是有序的集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0，所以必须采用顺序存储。
2、二分查找演示
下面是二分查找与顺序查找的演示图对比：
可以看出 二分查找 在查找数字 3 时只需3次，而 顺序查找 在查找3时需要3次。
3、二分查找原理
二分查找算法的原理如下：
假设在[begin，end)范围内搜索某个元素 v，mid == (begin + end)/ 2，end指的是数组的长度。
比较v与arr[mid]，有以下三种情况：
1)若 v < arr[mid]，则high = mid - 1；继续查找在左半区间进行；
2)若 v > arr[mid]，则low = mid + 1；继续查找在右半区间进行；
3)若 v = arr[mid]，则查找成功，返回 mid 值；
总结：如果大家有学习过二叉树知识，其实二分查找原理就是来自于二叉查找树(即：二叉平衡树)，所以查找的最大次数就是二叉树深度。
4、二分查找性能
二分查找最好时间复杂度是：最好情况下只需要进行1次比较就能找到目标元素；
二分查找最坏时间复杂度是：最坏情况就是查找不到目标元素，所需的时间复杂度可借助该序列的二叉树(二分查找判定树)形式进行分析：
序列[4,13,14,15,34,40,45,47,48,49,55]可以构建成下图所示的二叉树，以及查找对应的值14的过程图如下：
具有n个结点的二分查找树的深度为
5.代码模板
1 int binarySearch(int[] nums, int target) {
2 int left = 0;
3 int right = nums.length - 1; // 注意
4 while(left <= right) {
5 int mid = left + (right - left) / 2;
6 if(nums[mid] == target)
7 //这里根据具体情况设定
8 else if (nums[mid] < target)
9 left = mid + 1; // 注意
10 else if (nums[mid] > target)
11 right = mid - 1; // 注意
12 }
13 //其他特殊情况处理，主要是左右边界情况
14 }
二.常见题型
题型一：寻找一个数(基本的二分搜索)
比如我们给定数组如下动态图中，我们需要查找等于673的元素，如果存在，返回其索引，否则返回 -1。[left, right]
1 int binarySearch(int[] nums, int target) {
2 int left = 0;
3 int right = nums.length - 1; // 注意
4 while(left <= right) {
5 int mid = left + (right - left) / 2;
6 if(nums[mid] == target)
7 return mid;
8 else if (nums[mid] < target)
9 left = mid + 1; // 注意
10 else if (nums[mid] > target)
11 right = mid - 1; // 注意
12 }
13 return -1;
14 }
题型二：寻找左侧边界的二分搜索
比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9，我们需要查找第一个等于4的元素，「搜索区间」是[left, right]
1 int left_bound(int[] nums, int target) {
2 int left = 0, right = nums.length - 1;
3 while (left <= right) {
4 int mid = left + (right - left) / 2;
5 if (nums[mid] < target) {
6 left = mid + 1;
7 } else if (nums[mid] > target) {
8 right = mid - 1;
9 } else if (nums[mid] == target) {
10 // 别返回，锁定左侧边界
11 right = mid - 1;
12 }
13 }
14 // 最后要检查 left 越界的情况
15 if (left >= nums.length || nums[left] != target)
16 return -1;
17 return left;
18 }
题型三：寻找右侧边界的二分查找
比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9，我们需要查找最后一个等于4的元素，「搜索区间」是[left, right]
1 int right_bound(int[] nums, int target) {
2 int left = 0, right = nums.length - 1;
3 while (left <= right) {
4 int mid = left + (right - left) / 2;
5 if (nums[mid] < target) {
6 left = mid + 1;
7 } else if (nums[mid] > target) {
8 right = mid - 1;
9 } else if (nums[mid] == target) {
10 // 别返回，锁定右侧边界
11 left = mid + 1;
12 }
13 }
14 // 最后要检查 right 越界的情况
15 if (right < 0 || nums[right] != target)
16 return -1;
17 return right;
18 }
题型四：查找第一个大于给定值的元素
比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9,15,26,34,45，我们随便输入一个值，这个值可以是数组里面的值，也不可不在数组里面，查找出第一个比给定值大的元素。
1 /**
2 * 查找第一个大于给定值的元素
3 *
4 * @param nums 数组
5 * @param value 给定的值
6 * @return
7 */
8 private static int sercFirstOverVlaue(int[] nums, int value) {
9 int low = 0;
10 int high = nums.length - 1;
11 while (low <= high) {
12 int mid = low + ((high - low) >> 1);
13 if (nums[mid] > value) {
14 // 判断当前是第一个元素或者前一个元素小于等于给定值，则返回下标，如果前一个元素大于给定的值，则继续往前查找。
15 if ((mid == 0) || nums[mid - 1] <= value) return mid;
16 else high = mid - 1;
17 } else {
18 low = mid + 1;
19 }
20 }
21 return -1;
22 }
三.扩展题型(来自leetcode)
题目一：240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
思路：
这道题的关键在于得找到特殊位置的起始点，从该起始点，可以分治地去查找待查找地点。
主对角线上左上角和右下角不符合条件，因为
左上角的点，其周围的点都比它大，没法找到合适的查找路径
右下角的点，其周围的点都比它小，没法找到合适的查找路径
次对角线上左下角和右上角的点更合适，因为
左下角的点：往上比它小，往右比它大
右上角的点：往左比它小，往下比它大
因此，选择左下角或右上角的点都合适。
1 public boolean searchMatrix(int[][] matrix, int target) {
2 int n = matrix.length
3 int m = matrix[0].length;
4 int i = 0, j = m - 1; // 从右上角开始走
5 while(i < n && j >= 0) { // 最多会走到左下角去
6 int a = matrix[i][j];
7 if (a == target) return true;
8 if (a < target) i++; // 排除掉当前这一行, 往下走
9 else j--; // 排除掉当前这一列, 往左走
10 }
11 return false;
12 }
题目二：4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
解法一：直接找中位数
我们不需要将两个数组真的合并，我们只需要找到中位数在哪里就可以了。
1 public double findMedianSortedArrays(int[] A, int[] B) {
2 int m = A.length;
3 int n = B.length;
4 int len = m + n;
5 int left = -1, right = -1;
6 int aStart = 0, bStart = 0;
7 for (int i = 0; i <= len / 2; i++) {
8 left = right;
9 if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
10 right = A[aStart++];
11 } else {
12 right = B[bStart++];
13 }
14 }
15 if ((len & 1) == 0)
16 return (left + right) / 2.0;
17 else
18 return right;
19 }
空间复杂度：我们申请了常数个变量，也就是m，n，len，left，right，aStart，bStart 以及 i。时间复杂度：遍历 len/2+1 次，len=m+n，所以时间复杂度依旧是 O(m+n)O(m+n)。
总共 8 个变量，所以空间复杂度是 O(1)O(1)
解法二：二分查找
我们一次遍历就相当于去掉不可能是中位数的一个值，也就是一个一个排除。求两个有序数组的中位数，可以变换为，求第k个数。由于两个数组有序，我们每次只要从两个数组中，分别从左取k/2个数，然后想象尝试将这2组k/2个数合并。若第1组的最后一个数，小于第2组的最后一个数，则第1组不可能作为第k个数，那么可以将第1组的k/2个数全部排除。时间复杂度 O ( l o g ( m + n ) ) ，空间复杂度 O ( 1 ) 。
1 class Solution {
2 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3 int n = nums1.length, m = nums2.length;
4 int left = (n + m + 1)>>1;
5 int right = (n + m + 2)>>1;
6 int median1 = getKth(nums1, nums2, left);
7 int median2 = getKth(nums1, nums2, right);
8 return (median1 + median2) / 2.0;
9 }
10
11 private int getKth(int[] nums1, int[] nums2, int k) {
12 int n = nums1.length, m = nums2.length;
13 int i = 0, j = 0;
14 while (i < n && j < m && k > 1) {
15 int ie = Math.min(i + k>>1 - 1, n - 1);
16 int je = Math.min(j + k>>1 - 1, m - 1);
17 if (nums1[ie] <= nums2[je]) {
18 k -= (ie - i + 1); // 更新k
19 i = ie + 1; // 更新i, 注意不要先更新i, 再更新 k
20 } else {
21 k -= (je - j + 1);
22 j = je + 1;
23 }
24 }
25 if (i >= n) return nums2[j + k - 1];
26 if (j >= m) return nums1[i + k - 1];
27 return Math.min(nums1[i], nums2[j]);
28 }
29 }
题目三：33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
解题思路：二分查找
nums[0] <= nums[mid](0 - mid不包含旋转)且nums[0] <= target <= nums[mid] 时 high 向前规约；
nums[mid] < nums[0](0 - mid包含旋转)，target <= nums[mid] < nums[0] 时向前规约(target 在旋转位置到 mid 之间)
nums[mid] < nums[0]，nums[mid] < nums[0] <= target 时向前规约(target 在 0 到旋转位置之间)
其他情况向后规约
也就是说nums[mid] < nums[0]，nums[0] > target，target > nums[mid] 三项均为真或者只有一项为真时向后规约。
1 public int search(int[] nums, int target) {
2 if(nums.length==0){
3 return -1;
4 }
5 if(nums.length==1){
6 return nums[0]==target? 0:-1;
7 }
8 int n=nums.length;
9 int i=0;
10 int j=n-1;
11 while(i<=j){
12 int mid=i+(j-i)/2;
13 if(nums[mid]==target){
14 return mid;
15 // 如果mid在左边, 注意nums[mid]可能等于nums[0]
16 }else if(nums[0]<=nums[mid]){
17 // target也在左边
18 if(nums[0]<=target && target<nums[mid]){
19 j=mid-1;
20 }else{
21 i=mid+1;
22 }
23 // 如果mid在右边
24 }else if(nums[mid]<nums[0]){
25 // target也在右边
26 if(nums[mid]<target && target<=nums[n-1]){
27 i=mid+1;
28 }else{
29 j=mid-1;
30 }
31 }
32 }
33 return -1;
34 }
四.总结
我想大家对二分查找算法题目会遇到很多的写法，比如While判断逻辑中存在左闭右闭区间 [left,right]或左闭右开区间 [left,right)场景。不管是那种情况，都需要考虑边界条件，大家只需要考虑某一种判断逻辑即可，不需要全部记忆，增加负担。
1、二分查找算法具有三个作用：搜索目标值，搜索目标值的左边界(序列中最大的小于目标值的元素)，搜索目标值的右边界(序列中最小的大于目标值的元素)。
2、while循环的判断条件和搜索区间右边界right的赋值方式与right的初始化取值有关。right初始化为序列长度，则判断条件为left<right，赋值方式为right=mid；right初始化为序列长度-1，则判断条件为left<=right，赋值方式为right=mid-1。
3、二分查找三个作用的实现取决于while循环中对“序列中位数==目标值”这一情况的处理：
1 1、搜索目标值
2 if(nums[mid]==target)
3 return mid;
4
5 2、搜索目标值的左边界
6 if(nums[mid]==target)
7 right=mid; //最后结果左边界=right-1
8 或者
9 if(nums[mid]==target)
10 right=mid-1;//最后结果左边界=right
11
12 3、搜索目标值的右边界
13 if(nums[mid]==target)
14 left=mid+1;
我这里只给了大家<=的情况，大家如果不适应，可以留言给大家提供<的情况代码。
更多精彩关注wx公众号：
