在混沌纷繁的尘世中寻找真正想要的是什么
二分查找

概述


二分算法解决问题的使用条件

  1. 有序:数据必须是有序的,不管是顺序表还是链,这不必多说
  2. 二段性:二分算法的判断条件必须具有二段性,通常是 “>” 或 “<”,人话说就是可以分为两部分,也可以说“查找的目标元素可以进行比较操作”

在算法题中,用二分算法解决问题的充分条件是什么?

  1. 数据具有单调性:二分算法适用于有序数组或者单调性强的问题。在这种情况下,可以通过比较中间值和目标值的大小关系,排除一半的数据。
  2. 数据量较大:如果数据量较小,直接遍历整个数组即可。但如果数据量较大,二分算法可以节省大量时间复杂度,使算法效率更高。
  3. 没有重复元素:二分算法是基于元素唯一性的。如果存在重复元素,可能会出现一些问题,例如无法确定查找结果的唯一性。
  4. 可以随机访问元素:二分算法需要能够随机访问数组中的元素。如果数据结构不支持随机访问,例如链表,二分算法就无法使用。

模板代码

题目:

一道二分查找题

题干:满足 N ! 的末尾恰好有 K 个 0 的最小的 N 是多少?如果这样的 N 不存在输出 −1。

输入格式:一个整数K

输出格式:一个整数代表答案

样例输入:2

样例输出:10

标准答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
//求阶乘末尾0的个数其实就是求阶乘因子中5的个数
static long calc(long x) {
long res = 0;
while(x!=0) {
res=res+x/5;
x/=5;
}
return res;
}

public static void main(String[] args) {
//二分查找
Scanner scanner=new Scanner(System.in);
long k=scanner.nextLong();
long l=1,r=Long.MAX_VALUE-5;//l为最左边,r为最右边

while(l<r) {
long mid=(l+r)/2;
if(k<=calc(mid)) {
r=mid;
}else {
l=mid+1;
}
}
if(calc(r)!=k) {
System.out.print(-1);
}else {
System.out.print(r);
}

}
}

答案代码中,关于二分查找的分析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//二分查找规定要求f(x)中的x是有序的

//规定一个最小值和最大值的指针,但要注意后续两者相加后是否会超过基本数据类型范围上限
//在此题中,l为最左边下标,r为最右边下标
long l=1,r=Long.MAX_VALUE-5;

//当左下标小于右下标时循环
while(l<r) {
//每次循环之前算出中下标
long mid=(l+r)/2;

//如果中下标的值,在题目要求中偏小,把左下标的值更新为中下标
if(k<=calc(mid)) {
r=mid;
}else { //如果偏大,把右下标的值,更新为左下标
l=mid+1;
}
}


关于被查找的数组元素总数奇偶性的理解

GPT关于被查找的数组元素个数奇偶性的理解是:

一句话就是,以上模板无论数组元素个数是奇是偶都适用,不过当元素个数为奇则最后只会剩下一个元素没有争议;元素个数为偶时最后剩下两个元素,两者都有可能是要找的目标

这个二分查找算法是适用于所有元素个数为正整数的有序数组,无论数组元素个数是奇数还是偶数都可以使用这个模板。
对于奇数个元素的数组,最后剩下的中间元素就是要查找的元素;
对于偶数个元素的数组,则最后剩下的两个中间元素中任意一个都可能是要查找的元素。

一道题理解动态规划、BFS、DFS
宝贝,来春天玩
© 2024 Dal
「 就在那个时刻,你记得这并非幻觉,的确就在那个时刻,那只手和那块石头的接触面,她突然回过头冲你说:我也爱着你。 」