做新题，如果之前也有类似的题，多了就去掉，少了就补上
二分法的流程：
确保问题答案具有二段性（95%以上），另外还有5%的题目虽然不具有二段性，但仍可以使用二分法，例如每次都可以把区间缩小一半。
是二分的边界条件。
题目
升序排列的整数数组 在预先未知的某个点上进行了旋转（例如， 经旋转后可能变为 ）。
请你在数组中搜索 ，如果数组中存在这个目标值，则返回它的，否则返回 。
这个题目使用两次二分，第一次和上一题一样找到数组最小值，第二次二分是想找到target值。
代码：
方式二：以nums[0]作为分界条件。
2021年8月15日12:11:12：
题目
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
本题使用两次二分法，第一次使用二分法是为了找到第一个值等于target的下标，第二次使用二分法是为了找到最后一个值等于target的下标。
代码：
2021年8月15日14:39:25：
利用二分思想先找其左边界，再找其右边界即可，注意找左边界的时候，由右侧逼近；找右边界的时候，由左侧逼近，即可。
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
代码：
2021年8月15日15:18:03：
题目
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
代码：
2021年8月15日15:39:36：
很简单的二分：
注意mid*mid可能会越界，所以写成除的形式。
题目
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
示例 1：
这个题目首先将二维矩阵转化为一维数组，第一个数下标为0，最后一个数下标为nm-1;
代码：
2021年8月15日16:23:09：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
二分代码：
这一句：找到最小值最差情况下即数组元素全部相同的情况下需要O(n)的时间，因此最坏情况下复杂度为O(n)。所以我们也可以直接遍历这个数组，找到target即可：
直接遍历代码：
2021年8月15日17:13:17：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。
请找出其中最小的元素。
代码：
2021年8月15日17:36:21：
2021年8月15日17:46:16：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
说明：
这道题是 寻找旋转排序数组中的最小值 的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
这个题目类似于81题，虽然可以使用二分，但是如果全部元素均相同，则此时为最坏情况，时间复杂度为0（n）;
代码：
方法二：
2021年8月15日18:13:32：
题目
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
假设 nums[-1] = nums[n] = -∞ 。
注意：
这道题目虽然不具有明显的二段性，但仍可以使用二分法。
题目保证一定有解。
代码：
2021年8月15日18:43:22：
(这个题目方法严格来说不算二分法，但是有一点相似）
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
//暴力解法：直接遍历整个矩阵，时间复杂度为O(n*m),即两层for循环即可;
//方法二：从右上角元素值t开始枚举，如果t==target,则找到目标值，结束并返回即可；如果t>target,则说明t所在列均不可能有值为target，因为矩阵从左到右递增，从上到下也递增，所以我们此时可以去掉t所在这一列；如果t<target，由于矩阵从左到右递增，所以t所在行不可能有值等于target，所以我们此时可以去掉t所在这一行。所以每次，我们要么找到目标值，要么去掉一行或者一列，由于矩阵的行加列共n+m，所以我们最多会进行n+m次，所以时间复杂度为O(n+m);
代码：
2021年8月15日20:47:37：
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 指数。
指数的定义： 代表“高引用次数”（high citations），一名科研人员的 指数是指他（她）的 （ 篇论文中）总共有 篇论文分别被引用了至少 次。且其余的 篇论文每篇被引用次数 不超过 次。
例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
提示：如果 h 有多种可能的值，h 指数是其中最大的那个。
算法分析：
代码：
java代码：
java分析：
由于java实现数组倒序排列比较麻烦，所以这里我们转换思路。
排序
- 1、从小到大排序
- 2、从前往后枚举，找到最小满足即可，即满足中的个数使得每个对应的引用次数都比高
代码：
题目说到，指数是： 篇论文分别被引用了至少 次。通过排序后，若存在着在区间的篇论文，且每一篇论文引用的次数至少是次，即等价于在区间中引用次数最少的一定满足 被引用次数 次，即。在所有存在的情况下，找到最小的，则引用次数即一定最大。
2021年8月15日21:26:02：
2021年11月9日11:08:15：
题目
给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照 升序排列 。编写一个方法，计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）"
说明:
如果 h 有多有种可能的值 ，h 指数是其中最大的那个。
首先确定h的范围，h最大为n,最小为0；
本题具有二段性，即是否具有x个数，使得,一定是最后h个数>=h,所以我们需要看一下最后倒数h个数中最小的那个数是否满足>=h就可以了，记住前一段满足这个性质，而后一段不满足这个性质，
所以可以使用二分法；
代码：
2021年8月16日10:17:06：
2021年11月9日11:07:52：
题目
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version
是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
代码：
2021年8月16日10:43:293：
题目
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
抽屉原理：有N个抽屉和N+1个苹果，则一定至少有两个苹果在一个抽屉里。
我们使用1——n代表抽屉个数，即yl或者yr代表的是左/右抽屉个数，而我们枚举的cnt代表的是数组中落到l——m之间的个数，即苹果个数，注意和上面几道题目的区别。
代码：
2021年8月16日10:53:55：
非二分法：
转为142题寻找链表环的入口那个题目：
时间复杂度：O(n)
解法二：二分法：
算法
(分治，抽屉原理) 这道题目主要应用了抽屉原理和分治的思想。
可以解决重复的数不止一个的情况，
抽屉原理：n+1 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。
用在这个题目中就是，一共有 个数，每个数的取值范围是到，所以至少会有一个数出现两次。
然后我们采用分治的思想，将每个数的取值的区间划分成和两个子区间，然后分别统计两个区间中数的个数。
注意这里的区间是指 数的取值范围，即是数值，非下标，而不是 数组下标。
划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。
这个可以用反证法来说明：如果两个区间中数的个数都小于等于区间长度，那么整个区间中数的个数就小于等于n，和有n+1个数矛盾。
因此我们可以把问题划归到左右两个子区间中的一个，而且由于区间中数的个数大于区间长度，根据抽屉原理，在这个子区间中一定存在某个数出现了两次。
依次类推，每次我们可以把区间长度缩小一半，直到区间长度为1时，我们就找到了答案。
复杂度分析
时间复杂度：每次会将区间长度缩小一半，一共会缩小 次。每次统计两个子区间中的数时需要遍历整个数组，时间复杂度是 O(n)。所以总时间复杂度是 。
空间复杂度：代码中没有用到额外的数组，所以额外的空间复杂度是 。
// 划分的区间：[l, mid], [mid + 1, r]
2021年11月4日10:25:45：
转变为找环的入口那个题目：
2021年12月20日09:49:31：
2021年11月9日13:29:26：
2021年11月9日13:39:42：
题目描述
给定长度为n的数组，每个元素代表一个木头的长度，木头可以任意截断，从这堆木头中截出至少k个相同长度为m的木块。已知k，求max(m)。
输入两行，第一行n, k，第二行为数组序列。输出最大值。
解释：如图，最多可以把它分成5段长度为4的木头
ps:数据保证有解，即结果至少是1。
题目分析
方法一：暴力。大概思路就是从1遍历到木棍最长的长度，每次遍历的长度作为m，如果可以将所有木头截出来k个长度为m的木块，则更新最大值，最后输出最大值即可。可以通过下面的伪代码片段辅助理解：
上面的代码也比较容易理解，这里就不多展开说了。时间复杂度也很容易看出来是O(n * len), len为木头中最大的长度。容易想到遍历长度时可以从大到小遍历，if (cnt >= k)成立，则该值即为最终结果，可直接break，但最坏时间复杂度没变。
方法二：二分。方法一在[1,max]寻找最大长度时是顺序遍历，由于其有序，我们可借助二分来快速检出结果。如果能截出来k个长度为x的木块，说明答案肯定 >= x，则接下来只需在[x,max]中找m最大满足条件的长度。反之则说明答案 < x，则在[1,x-1]中寻找结果。这样我们每次可以舍弃1/2的情况，因此使用二分的时间复杂度是O(n * log Len)。