二分查找的理解
今天的每日一题遇到了有关二分查找类型的题目，感觉之前虽然看到过，但是还是得总结一下技巧，对相似的类型进行归纳总结。
二分查找的模板
1. 例子：搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 22. 解答分析
-
对于此类问题，暴力解答的时间复习度为
，但是如果需要降低复杂度的话，可以利用二分的思想进行解答。也就是设置左侧下标和右侧下标，接着再对中间的下标进行计算。 -
每次根据此时的
nums[mid]和target进行比较，相等直接返回下标；num[mid]<target的话，说明此时的left需要左移；nums[mid]>target的话，说明此时的right需要右移。 -
要是查找结束之后都不存在呢？可以返回
left,此时的是插入的位置；当然，在每次循环的过程中是对left还是right进行加减判断的，需要根据具体的边界条件有所调整。
3. 具体代码
//写法1：左闭右闭区间，此时遍历完成后不满足情况，会返回左边界值
class Solution{
public int searchInsert(int[] nums,int target){
int left=0,right=nums.length-1;
while(left<=right){ //注意此时的左右边界值是可以重合的
int mid=(left+right)/2;
if(nums[mid]==target){
return mid; //相关的逻辑需求值
}else if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
// 都不满足的话，返回的值
return left;
}
}
//写法2：左闭右开的区间，此时遍历完成后不满足情况，若左右边界值重合的话，说明此时退出循环，可以返回left或者right值，因为不会再次遍历了
class Solution {
public int searchInsert(int[] nums, int target) {
int left=0;
int right=nums.length;
while(left<right){
int mid=left+(right-left)/2; //防止边界溢出的情况，比如left和right都很大（如：1e6），会产生溢出；
if(nums[mid]>target){
right=mid;
}else if(nums[mid]<target){
left=mid+1;
}else return mid;
}
return right;
}
}-
上述的代码写起来，最后取得是right还是left不太清晰，这里具体说明一下：
-
其实可以这么理解，没有找到时，l与r肯定反了，不够成区间，且相差不会超过1。
-
- 此时有可能是l右移超过了r，那l=mid + 1，mid肯定是小于target了，那现在mid+1就是第一个不小于target可以插入的位置，为啥不是r呢，发生交叉时l与r是相等的，那既然是l右移，说明r是最后一个小于target的数
- 反过来，如果r=mid-1，导致lr反叉，则mid是大于了target的，则mid-1是最后一个小于target的数，那mid-1 的下一个位置就是插入位置，即l
-
这些其实原理是在：所有的lr反转前lr肯定是相遇了的，然后另外一个核心是mid是向下取整重叠到l的，这才有上面的结果。
-
4. 初步模板
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1; // 注意
while(left <= right) { // 注意是否可以取等，以及区间是否是闭or开
int mid = (left + right) / 2; // 注意
if(nums[mid] == target) { // 注意
// 相关逻辑
} else if(nums[mid] < target) {
left = mid + 1; // 注意
} else {
right = mid - 1; // 注意
}
}
// 相关返回值,参考前面题目的方法1
return 0;
}
}
Leetcode. H 指数
1. 题目说明
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。
示例 1：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。2. 解答分析
-
这个题目也太绕了，理解一下题目中给出的定义：
N篇论文中总共有h篇论文分别被引用了至少h次；- 其余的
N - h篇论文每篇被引用次数不超过h次。
-
h指数其实指的是论文的数量，而不是引用的次数。可以理解为先将
论文被引用的次数进行升序排序，找到一条分割线|，使得分割线右侧的最少引用次数（数值）>=分割线右边的论文数量（个数），所以总的来说，返回的还是一个论文的数量的问题，也就是分割线右侧论文数量的问题。 -
所以我们可以确定使用的是
二分查找的思想：-
首先确定整数的范围：
- 最好的情况下，所有论文的每个被引用次数>=总共论文的篇数，此时的h指数为（长度）为n。
- 最差的情况下，所有论文被引用的次数都为0，此时的h指数的（长度）为0。
得到整数的区间为
[0...len]，所以此时的left=0,right=len;（初始值） -
二分查找，先猜想一个中间的论文篇数
int mid = (left + right + 1) / 2,需要向上取整；比如[0,1]，mid=0不是向上取整（+1）的话，会一直是0; -
论文篇数和被引用次数的关系是：「高引用的被引用次数 >= 高引用的论文数」，这些论文才可以被称为「高引用」。因此在二分查找的循环体内部，可以遍历一次数组，数出大于等于
mid的论文篇数。- 如果大于等于 mid 的论文篇数大于等于 mid ，说明 h 指数至少是 mid。例如 [0,1,|3,5,6]，引用次数大于等于 2 的论文有 3 篇，说明答案至少是 2，最终答案落在区间 [mid…right] 里，此时设置 left = mid；
- 反面的情况不用思考，因为只要上面分析对了，最终答案落在区间 [mid…right] 的反面区间 [left…mid - 1] 里，此时设置 right = mid - 1。
-
3. 具体代码
public class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
int left = 0;
int right = len;
while (left < right) { //左闭右开
// 猜论文篇数
int mid = (left + right + 1) / 2;
// 满足高引用的特点是：引用次数 >= 论文篇数
// count 的含义是：大于等于 mid 的论文篇数
int count = 0;
for (int citation : citations) {
if (citation >= mid) {
count++;
}
}
if (count >= mid) {
left = mid;
} else {
right = mid - 1;
}
}
return left; //此时return right;也是可以通过的。
}
}-
复杂度分析：
-
时间复杂度：
二分循环
次，每一次都需要看一遍数组； -
空间复杂度：
只利用到了常数个变量；
-
-
补充一张图，解释上述的最右边界值的问题，和mid的取值问题：(也称为二段性)，给出下面的代码解释：
int l=0,r=n-1; while(l<r){ int mid=(l+r)/2; if(nums[mid]>=target){ r=mid; } else{ l=mid+1; } } return l; int l=0,r=n-1; while(l<r){ int mid=(l+r+1)/2; if(nums[mid]<=target){ l=mid; }else{ r=mid-1; } } return l; //这里的返回值是l或r都可以，注意退出循环的条件是l==r;
