字节面试居然倒在这道算法基础二分算法上，现在才搞懂，哭了

　　一、定义
　　二分查找也称折半查找（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;     }