算法基础---二分算法
一、定义
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二、查找过程
在一个有序序列中，取中间值把序列分成两边，先看中间值，如果中间值小于要查找的值，那么说明目标值一定在
右边；如果中间值大于目标值，那么目标值一定在左边；如果中间值等于目标值，那么查找完成。
以猜数字游戏为例，小明想一个0-1000的数，小红来猜。
小明选的是623为例：
小红：大于500吗？
小明：yes
小红：那么一定在[501，1000]之间，大于750吗？
小明：no
小红：那么一定在[501，750]之间，大于625吗？
小明：no
小红：那么一定在[501，625]之间，大于563吗？
小明：yes
小红：那么一定在[564，625]之间，大于594吗？
小明：yes
小红：那么一定在[595，625]之间，大于610吗？
小明：yes
小红：那么一定在[611，625]之间，大于618吗？
小明：yes
小红：那么一定在[619，625]之间，大于622吗？
小明：yes
小红：那么一定在[623，625]之间，大于624吗？
小明：no
小红：那么一定在[623，623]之间，你想的数字是623
小明：yes。
对于1-1000之间的猜数字游戏，最多只需要10次就能找到。
二分查找算法的时间复杂度是O(logN)
三、框架
二分查找的框架大致如下：
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length-1;
int mid = l + (r-l)/2;
while(l < r){
//能找到，直接返回元素下标
if(nums[mid] == target)
return mid;
else if(nums[mid] < target){
l = mid + 1;
mid = l + (r-l)/2;
}
else{
r = mid-1;
mid = l + (r-l)/2;
}
}
//未找到
return -1;
}
注意：
1、中间值mid取法
应该用 mid = l + （r-l）/ 2 ，而不是 mid = (l + r) / 2，因为如果 l 和 r都很大，那么（l + r）将会溢出整数范围。
2、偶数个数的中间值
如果数字的总数是偶数，那么中间值有两个，按照 mid = l + （r-l）/ 2 算的话，中间值应该是左边那个。例如对于1、2、3、4，l = 0，r = 3，
mid = 0 + （0+3）/ 2
=0 + 1
= 1。
因为mid、l、r都是int类型，如果有小数部分，会自动舍弃。
四、例题
1、搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
题目来源：力扣（LeetCode）
解题思路：先使用二分查找，如果能找到，直接返回元素下标；
接下来讨论不能找到的情况：
第一种情况，二分查找结束后，目标值大于mid
以[1，3，5，6，9] 和目标值 4为例
初始状态：
第一遍二分查找结束：
第二遍二分查找结束：
两遍查找结束之后，发现mid小于目标值4，此时，4应该插入在3后面，所以返回 mid+1。
第二种情况，二分查找结束后，目标值小于mid
以[1，3，5，6，9] 和目标值 7为例，
初始状态：
第一遍二分查找后：
第二遍二分查找后：
两遍查找结束之后，发现mid大于目标值7，此时，7应该插入在9前面，所以返回 mid。
题解代码：
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length-1;
int mid = l + (r-l)/2;
while(l < r){
//能找到，直接返回元素下标
if(nums[mid] == target)
return mid;
else if(nums[mid] < target){
l = mid + 1;
mid = l + (r-l)/2;
}
else{
r = mid-1;
mid = l + (r-l)/2;
}
}
//第一种情况，二分查找结束后，目标值大于mid
if(nums[mid] < target)
return mid+1;
//第二种情况，二分查找结束后，目标值小于mid
else
return mid;
}
2、搜索二维矩阵
题目来源：力扣（LeetCode）
解题思路：
既然题目提到了要编写一个高效的算法，那么用两个for循环暴力枚举肯定是不行的。
再看一遍题目，该矩阵具有以下特性：同一行，右边的数要大，同一列，下面的数要大。由此我们可以发现，如果我们取一个数作为右上角，那么比该数小的一定在其左边的列之中，比该数大的一定在该数的下面的行之中。
例如：
对于下面矩阵，我们取7作为右上角的数，那么比7小的一定在第0、1、2列，比7大的一定在第1、2、3行。
假设我们要找11，那么首先取右上角7，发现7比11小，因为7是第一行最大的，所以第一行不可能再找到11，剔除第0行；从第1行开始找，同样，从右上角20开始看，20大于11，所以第3列一定不可能找到11，因此我们剔除第3列；之后，16作为右上角，16大于11，剔除第2列；11作为右上角，找到目标数。
简单来说就是：从右上角开始找，
右上角的数 = 目标，结束查找，返回true；
右上角的数 < 目标，剔除该行；
右上角数 > 目标，剔除该列。
程序结束也未找到，返回false。
题解代码：
public boolean searchMatrix(int[][] matrix, int target) {
for(int i = 0;i < matrix.length;i++){
for(int j = matrix[0].length-1;j >=0;j--){
//从右上角开始搜索
//如果右上角数字为目标数字，返回true
if(matrix[i][j] == target)
return true;
//如果右上角数字小于目标数字
//说明该行都小于目标数字，剔除该行
else if(matrix[i][j] < target)
break;
//如果右上角数字大于目标数字
//说明该列都大于目标数字，剔除该列
else
continue;
}
}
//没有找到
return false;
}
原文链接：邱子林的博客