二分法(java)

目录

  • 一、简介:
  • 二、模板:
  • 三、例题:

一、简介:

二分法是一种常见的算法思想,也称为二分查找、折半查找。其核心思想是通过将目标数据与有序的数据序列进行比较,每次查找都将数据序列一分为二,确定目标数据在哪一半中,直到找到目标数据或者确定目标数据不存在。
具体步骤如下:

  1. 将数据序列按照某种方式排序(一般是从小到大)。
  2. 确定要查找的目标数据。
  3. 确定查找的范围,在数据序列的左边界和右边界之间。
  4. 每次将查找的范围一分为二,找到中间位置的数据,与目标数据进行比较。
  5. 如果中间位置的数据等于目标数据,则查找成功,返回该位置;否则,判断目标数据在左边还是右边,缩小查找的范围。
  6. 重复第4步至第5步,直到找到目标数据或者确定其不存在。

二分法的时间复杂度为 O(log n),相比于顺序查找的 O(n),效率更高。二分法适用于有序的数据序列,例如数组、有序链表等。

重点先排序,在查找。

二、模板:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int l = 0, r = 1000000000;int res = 0;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) {res = mid;l = mid + 1;}else {r = mid - 1;}}}private static boolean check(int mid) {// TODO Auto-generated method stubreturn false;}
}

三、例题:

acwing:1460.我在哪?

农夫约翰出门沿着马路散步,但是他现在发现自己可能迷路了
沿路有一排共 N 个农场。
不幸的是农场并没有编号,这使得约翰难以分辨他在这条路上所处的位置。
然而,每个农场都沿路设有一个彩色的邮箱,所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A…Z 之间的一个字母来指定,所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A…Z 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 K 的值,使得他查看任意连续 K 个邮箱序列,他都可以唯一确定这一序列在道路上的位置。
例如,假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K=3,因为如果他看到了 ABC,则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K=4,因为如果他查看任意连续 4 个邮箱,那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 N,第二行包含一个由 N 个字符组成的字符串,每个字符均在 A…Z 之内。
输出格式
输出一行,包含一个整数,为可以解决农夫约翰的问题的最小 K 值。
数据范围
1≤N≤100
输入样例:
7
ABCDABC
输出样例:
4

代码示例

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static int n;static String str;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();str = sc.next();int lo = 0, hi = n;while (lo < hi) {//二分查找第一个不能达到的kint mid = (lo + hi) >> 1;if (check(mid)) {lo = mid + 1;}else {hi = mid;}}System.out.println(lo);}private static boolean check(int k) {// TODO Auto-generated method stubList<String> list = new ArrayList<>();String s;for (int i = 0; i + k <= n; i++) {s = str.substring(i, i + k);if (list.contains(s)) {return true;}list.add(s);}return false;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/8.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Docker consul的容器

consul服务更新和服务发现 什么是服务注册与发现 服务注册与发现是微服务架构中不可或缺的重要组件。起初服务都是单节点的&#xff0c;不保障高可用性&#xff0c;也不考虑服务的压力承载&#xff0c;服务之间调用单纯的通过接口访问。直到后来出现了多个节点的分布式架构&…

优维低代码实践:模板

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。…
最新文章