算法刷题入门数据结构|二分查找

一.二分查找基础

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公众号：