失眠网 > LeetCode算法题4：二分查找及扩展应用

LeetCode算法题4：二分查找及扩展应用

时间：2019-01-17 03:11:46

文章目录

前言一、二分查找二、第一个错误的版本三、搜索插入位置总结

前言

Leetcode算法系列：https://leetcode-/study-plan/algorithms/?progress=njjhkd2

简单介绍总结一下二分查找相关的算法题：

一、二分查找

题目链接：https://leetcode-/problems/binary-search/

题目描述：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路：直接采用通用的二分查找算法即可：

class Solution {public int search(int[] nums, int target) {int start=0,end=nums.length-1,mid;while(start<=end){mid=(start+end)/2; // 最好改为：mid = start+（end-start）/2;if(nums[mid]==target)return mid;else if(nums[mid]<target)start=mid+1;elseend=mid-1;}return -1;}}

1，取 mid 值时，采用 mid = start+（end-start）/2; 可以避免当 start 和 end 很大时造成的整数（int）越界。

2，循环结束条件为 start<=end，所以在 while 循环退出时有 start>end，（在此为 start=end+1）。

3，二分查找的时间复杂度为 O(logn)，因为每次循环都会将待处理数组的规模缩小一半。

二、第一个错误的版本

题目链接：https://leetcode-/problems/first-bad-version/

题目描述：你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

思路：保持之间的二分查找框架不变，修改循环退出条件为当前版本正确且上一个版本错误，

public class Solution extends VersionControl {public int firstBadVersion(int n) {if(isBadVersion(1))return 1;int start=2,mid; //区间为[2,n].while(start<=n){//还是按照二分查找的思路来做mid=start+(n-start)/2;if(!isBadVersion(mid)) //缩小区间到[mid+1,n]start=mid+1;else if(!isBadVersion(mid-1)) //如果mid为true，mid-1为false，返回mid即可return mid; else //如果mid-1不是false，缩小区间到[start,mid-1]n=mid-1;}return -1;}}

缺点时要调用两次 isBadVersion函数。

Version2：修改循环判定条件为start<end，在循环退出时的 start 或 end 为我们感兴趣的下标值。并采用合理的缩小规模方式在循环内仅调用一次 isBadVersion 函数。如下：

public class Solution extends VersionControl {public int firstBadVersion(int n) {int start=1,mid;while(start<n){mid=start+(n-start)/2;if(!isBadVersion(mid))start=mid+1;elsen=mid;}return start;}}

上述算法看起来很巧妙，甚至成功的有点侥幸，因为在每次计算 mid 值时，由于向下取整，所以有时候会出现 mid==start 出现，而不会存在 mid==n 出现。因此令 n=mid；这样在每次循环时区间规模总会缩小，直至得到最终结果。

在缩小区间时，最好不要采用 start==mid，很有可能区间不会缩小，陷入死循环。比如当要求找到最后一个正确的版本时会发生这种情况。

三、搜索插入位置

题目链接：https://leetcode-/problems/search-insert-position/

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

思路：采用通用的二分查找框架，如果目标值存在于数组中，由 mid 给出其返回下标；如果不存在的话，由 start 或 end+1 给出返回下标。

class Solution {public int searchInsert(int[] nums, int target) {int start=0,end=nums.length-1,mid;while(start<=end){mid=start+(end-start)/2;if(nums[mid]==target)return mid;else if(nums[mid]<target)start=mid+1;elseend=mid-1;}return start; //关键点在于确定最后一个查找区间和target之间的关系。//return end+1;}}

由 start 或 end+1 给出返回值下标的原因在于：在一个不含目标值的升序数组中采用通用的二分查找算法查找 target 的位置，在循环结束后 end 处的值刚好小于 target；start 处的值刚好大于 target。比如对于数组 [1,3,4,6,7]，查找 5 所在位置：循环结束后 start =3，end = 2。

Version2：修改循环判定条件为start<end，在循环退出时的 start 或 end 为我们感兴趣的下标值。如下：

public int searchInsert(int[] nums, int target) {int end=nums.length-1,start=0,mid;// 特殊判断if (nums[end] < target) return end+1;// 程序走到这里一定有 nums[end] >= target，保证插入位置在区间 [start..end]while(start<end){mid=start+(end-start)/2;if(nums[mid]<target)start=mid+1;// 下一轮搜索的区间是 [mid + 1..end]elseend=mid;// 下一轮搜索的区间是 [start..mid]}return end;}

和二、查找错误的版本类似：在循环中令 end=mid 来保证循环执行结束。