一、前言
盲目刷题只会让自己心态爆炸，所以本期14天算法学习计划，也是LeetCode上的 [算法] 学习计划，在本专栏的每一篇文章都会整理每一天的题目并给出详细题解，以及知识点的整理
二、知识点
第一天的知识点是二分查找，也是一个较简单的查找算法，但是在做题时不能只想着去套模板解题，而是要根据题目意思来使用二分查找的算法解决问题，有关于二分查找的知识点我已经整理在一篇文章里了，想要复习知识点或者对它还一知半解的可以阅读一下
算法查找——二分查找
三、LeetCode704. 二分查找
1.题目
LeetCode704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1
输入: nums = [-1,0,3,5,9,12]， target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2
输入: nums = [-1,0,3,5,9,12],，target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
2.解题示意图
原始定义的 left 、right 和 mid
如果要找的 targe 比 mid 指向的值大，就在右半边找（绿色为新的 left 和 mid ）
可见left的值应该修改为mid+1
如果要找的 targe 比 mid 指向的值小，就在右半边找（绿色为新的 left 和 mid ）
可见 right 的值应该修改为 mid-1
3.解题思路
1.先查找数组中最中间的元素mid（下标值向下取整）
2.如果要查找的元素值比中间的元素大，就将最大值改为中间值减一
max = mid - 1
3.如果要查找的元素值比中间的元素小，就将最小值改为中间值加一
min = mid + 1
4.重复上述步骤，直至找到所要查找的元素
4.注意事项
很多小伙伴可能第一次刷题的时候会设mid = (left + right)/2，但是如果数据的值大就会溢出。想不明白为什么会溢出？别急，接着往下听我分析
如果我们规定整数的最大值只能是100的话，如果有个老六偏要设数组头和尾的值都是99的话，99+99=198 > 100，芭比Q了，这不就没办法运行程序了嘛，所以为了避免出现这种错误，只能用减法，由于数组的下标值是依次递增的，要想知道他的一半是多少的话，直接拿最大值-最小值的差除以2再加上最小值（一秒回到小学），即 mid = left + (right - left) / 2
如果不相信的话，可以举例试试，比如6到99的中间值是多少？（99-6）/ 2 + 6 = 52，（99+6）/ 2再向下取整（Java内部自动的）也是52，完全没问题
5.代码实现
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] < target){ left = mid + 1; } else if(nums[mid] > target){ right = mid - 1; } else{ return mid; } } return -1; } }
6.验证代码
四、LeetCode278. 第一个错误的版本
1.题目
LeetCode278.第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1
输入：n = 5, bad = 4
输出：4
解释： 调用 isBadVersion(3) -> false
调用isBadVersion(5) -> true
调用isBadVersion(4) -> true
所以，4 是第一个错误的版本
示例2：
输入：n = 1, bad = 1
输出：1
2.解题示意图
这道题看完第一眼，这题目是什么意思？？？纯纯黑人问号，所以接下来我会一点一点剥开它，显出原形——二分查找
我们先定义n为10，如果一个个去查找他是不是正确的话，实在是太麻烦了，那么直接一下子砍一半，看中间，也就是第5个版本，发现他这个版本出错了（这道题比较容易让人晕乎的点在此：true表示这个版本是错误的）
既然我们要找出第一个错误的版本，题目里面又告诉我们 “错误的版本之后的所有版本都是错的 ”所以不用看5以后的版本，都是错的，只需要看5版本之前的，也同样先砍一半看最中间的，所以要修改right的值，即 mid = true 时，right = mid
发现是3是false：这个版本不是错误的（是正确的），也就是说3版本是正确的
那此时我们就要修改left的值，即 left = mid+1去判断mid后一个的值，发现重合了，我们就返回left的值就好了
3.解题思路
1.找出中间的元素mid，并判断是否是错误版本
2.如果是错误版本**（mid = true）**，则修改right的值，使得 right = mid
3.如果是正确版本（mid = false），则修改left的值，使得
4.注意事项
- false：这个版本不是错误的，即该版本正确
- true：这个版本是错误的
- mid = left + (right - left) / 2
5.代码实现
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { int left = 1; int right = n; while(left < right){ int mid = left + (right - left)/2; if(isBadVersion(mid)){ right = mid; } else{ left = mid +1; } } return left; } }
6.验证代码
五、LeetCode35. 搜索插入位置
1.题目
LeetCode35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3
输入: nums = [1,3,5,6], target = 7
输出: 4
2.解题思路
1.先查找数组中最中间的元素mid（下标值向下取整）
2.当left <= right时，通过循环查找元素
3.如果要查找的元素值比中间的元素大，就将最大值改为中间值减一
right = mid - 1
4.如果要查找的元素值比中间的元素小，就将最小值改为中间值加一
left = mid + 1
5.重复上述步骤，直至找到所要查找的元素
6.如果没有，就返回left的值；因为要插入的元素是要把比这个元素大的向后移位，而比这个元素小的是不会改变的，所以其下标值为最后搜索的两个元素的后面，如[1,3,5,7,9]，target=4，
第一次mid的值为2，元素为5，
第二次mid值为1，值为3，由于搜索不到，但是left（下标0）和right（下标1）并没有重合，且 target > nums[mid] 所以又要修改left的值为 left = mid+1 = 2，那么left > right 所以退出循环，返回的值为left
这里第五步有点绕，建议配合代码食用
3.代码实现
class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right){ int mid = left + (right - left) / 2; if(target > nums[mid]){ left = mid + 1; } else{ right = mid - 1; } } return left; } }
4.验证代码
六、结语
最后一道题的解题方法是我自己优化了官方的解题方法后实现的，虽然理解比较困难，但是一定程度上优化了代码，如果有更加高效的解题方法，欢迎评论留言
