刷题笔记三：二分法

来啦来啦，今天咱们继续刷题笔记三。
建议初学者跟着我一起打卡，一个知识点一个知识点的刷题，效率会更高。还是跟上面的笔记一样，总结来源于作者高畅的LeetCode101, 题目都是来自leetcode, 欢迎讨论与指正！

核心：每次查找时通过将待查找区间分成两部分并只取 一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n) 的数组，二分查找的时间复 杂度为 O(log n)。
举个栗子：给你从1到100 的数组要求你找出我要的目标数，我的目标数是60， 在你并不知道目标数的情况下，如果从1开始遍历，你要猜60下才能到达60， 然而如果我们采用二分法，即每次从数组的中间数粗发向目标靠拢，则是先猜50，现在数组被一分为二，目标数大于50，则再从50到100中取中间数，这样继续循环下去直到猜到目标数。
你会发现二分法查找比一般传统的查找要快很多。

涉及问题：
1.        求开方
1)        Lc 69. Sqrt(x)： 给定一个非负整数，求它的开方，向下取整。
题解：我们可以把这道题想象成，给定一个非负整数 a，求 f (x) = x2 − a = 0 的解。因为我们只考 虑 x ≥ 0，所以 f(x) 在定义域上是单调递增的。考虑到 f(0) = −a ≤ 0，f(a) = a2 − a ≥ 0，我们 可以对 [0, a] 区间使用二分法找到 f (x) = 0 的解。
2.        查找区间
1)        Lc 34. Find First and Last Position of Element in Sorted Array： 给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。
题解：先创一个helper function 用来找target 的位置，即用二分法开始查找，左右两个指针分别指向数组的最小最大值，每次取数组的中间值，如果中间值小于target,那么我们可以就排除从左指针到中间值的所有数，则移动左边的指针，即left = mid+1，开始新的数组即mid+1到right这组数的收索。
建好helper function 之后，我们开始遍历整组数两次，第一次找到target之后继续往左边收索查看是否有更靠左的值，第二次找到target之后继续往右边收索查看是否有更靠右的值。确定好是最edge 的值后返回这个值。
3.        旋转数组查找数字
1)        Lc 81. Search in Rotated Sorted Array II： 一个原本增序的数组被首尾相连后按某个位置断开(如 [1,2,2,3,4,5] → [2,3,4,5,1,2]，在第一 位和第二位断开)，我们称其为旋转数组。给定一个值，判断这个值是否存在于这个为旋转数组 中。
题解：这道题是33题的升级版，不同于33题的是这道题里的数组可以允许重复的数字。首先我们要清楚这个数组被分为了两个部分，left sorted portion and right sorted portion，然后判断出中间值落入哪个部分，如果落入左边部分，则要判定target 是在中间值的左边还是右边，注意这里需要用到左指针的值与中间值一起来判定target值与中间值的关系。反之，若中间值在右边部分，则也是要判定target 是在中间值的左边还是右边，这里则需要用到右指针与中间值来判定。Binary search 之前我们还需要在写两行代码来把指向重复的值的指针一直往下推下去，即左边指针往右靠，右边的指针往左靠，这样就能继续我们的二分法查找。

练习题：
基础：154， 540.
进阶：4.
笔记持续更新，小伙伴记得关注我，点赞➕收藏呀！一起加油～