二分查找模板
二分查找模板
最新推荐文章于 2024-07-21 15:38:00 发布

Zyy~ 于 2021-01-30 14:14:45 发布
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
import java.util.ArrayList;
public class a {
public static int bSearch(int arr[],int target)
{
int n=arr.length;
int l=0;
int r=n-1;
while(l<=r)
{
int mid=l+(r-l)/2;
if(arr[mid]==target) return mid;
if(arr[mid]>target) r=mid-1;
else l=mid+1;
}
return -1;
}
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
System.out.println(bSearch(arr,0));
}
}
测试:输入:5
输出:4
输入:0
输出:-1
经典例题: 275. H 指数 II难度中等83
给定一位研究者论文被引用次数的数组(被引用次数是非负整数),数组已经按照 升序排列 。编写一个方法,计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)总共有 h 篇论文分别被引用了至少 h 次。(其余的 N - h 篇论文每篇被引用次数不多于 h 次。)"
示例:
输入: citations = [0,1,3,5,6] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。 由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3。
说明:
如果 h 有多有种可能的值 ,h 指数是其中最大的那个。
进阶:
这是 H 指数 的延伸题目,本题中的 citations 数组是保证有序的。你可以优化你的算法到对数时间复杂度吗?通过次数17,108提交次数41,748
代码:class Solution {
public int hIndex(int[] citations) {
int n=citations.length;
if(n==0) return 0;
int l=0;
int r=n-1;
while(l<=r)
{
int mid=l+(r-l)/2;
if(citations[mid]==n-mid) return n-mid;
if(citations[mid]>n-mid) r=mid-1;
else l=mid+1;
}
return n-l;
}
}
相关知识
2251. 花期内花的数目(cpp内置二分查找)
查找和替换字符类中的花括号
Wireshark搜索/查找字符串失败
KMP 字符串匹配 SDNU 1100 字符串查找 HDU 2087 剪花布条
作业打卡 设置密码 &水仙花数& 查找字符串
花期内花的数目【离散化+前缀和+差分】
nyoj685查找字符串(字典树)
在C#中跨多个列表查找公共项的最快方法
鲜花网站模板
外国节日PPT模板
原文链接: 二分查找模板 https://www.huajiangbk.com/newsview126647.html
| 上一篇: 庆典花卉图片 | 下一篇: 黄金庆典一年开几次花(3 |





