二分查找(Binary Search)
1. 定义
折半查找
2. 数据要求
线性表、有序（哪头大或哪头小）（例如：排序后的数组）
3. 算法
- 非递归、循环实现二分查找
class Solution {
public int search(int[] nums, int target) {
if (nums == null) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;// 防止计算时溢出
if(target > nums[mid]) {
start = mid + 1;
} else if(target < nums[mid]) {
end = mid - 1;
} else
return mid;
}
return -1;
}
}
可用递归实现二分查找
mid = start + (end - start) / 2;：获得中间游标，用减法确保类型范围
每次循环，通过比较更新查找的范围：[start,end]——start = mid + 1; 或 end = mid - 1;
start <= end：两个游标相遇则结束循环
4. 优点、缺点
- 优点：查找次数MAX：数据（数组）长度/ 2（整除）、折半查找的时间复杂度为O(logn)，远远好于顺序查找的O(n)
- 缺点：虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间
5. 例题
两道来自 leetcode 的题
1、搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素
class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
int mid = 0;
while(start <= end) {
mid = start + (end - start) / 2;// 防止计算时溢出
if(nums[mid] == target) {
return mid;
}
if(nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
}
查找过程和上面代码一样
return start;：没法查找到存在的返回值。这个值就是目标值理应按顺序插入的位置（从0开始数）
2、第一个错误的版本
由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
错了之后的版本是可以判对的
减少判断次数（调用API ）那么根据判错实现对连续的版本号划分区域，从而使用二分法求解
第一个错的版本，他的前面一个版本是被API判错的，例如：输入5，5这样的数据，可以先直接调用API传入4得到false值
再看调用举例，3，5，4：从而推导出每次调用API时传值的计算式
根据调用返回的结果，划分版本号的调查区域。True则为左边的版本号可能出现第一个错误，故start更改；false则为右边的版本号可能出现第一个错误，故n更改
当start、n两个游标相遇，结束循环
返回start的值
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
if(!isBadVersion(n - 1)) {
return n;
}
int start = 0;
while(start <= n) {
int mid = start + (n - start + 1) / 2;// 防止计算时溢出
if(isBadVersion(mid)) {
n = mid - 1;
} else
start = mid + 1;
}
return start;
}
}
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { // if(!isBadVersion(n - 1)) { // return n; // } int start = 1; while(start < n) { int mid = start + (n - start) / 2;// 防止计算时溢出 if(isBadVersion(mid)) { n = mid; } else start = mid + 1; } return start; } }这个版本才为妥善。start从0开始是一种错误的写法，某种极为特殊的情况下会错误
