首页 > 其他分享 >二分查找变形

二分查找变形

时间:2023-03-29 19:23:45浏览次数:42  
标签:二分 Arrays 变形 System param int 查找 println out

package test;

import java.util.Arrays;

public class N172 {
	public static void main(String[] args) {
		int[] a = { 1, 34, 4, 4, 5, 4, 6, 2345, 0 };
		Arrays.sort(a);
		System.out.println(Arrays.toString(a));
		System.out.println(search(0, a.length - 1, 4, a));
		System.out.println(search2(0, a.length - 1, 4, a));
	}

	/**
	 * 找到第一个大于 x 的数的下标
	 * 
	 * @param l
	 * @param r
	 * @param x
	 * @param a
	 * @return
	 */
	static int search(int l, int r, int x, int[] a) {
		while (l <= r) {
			int mid = (l + r) / 2;
			if (x < a[mid]) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return l;
	}

	/**
	 * 找到第一个小于 x 的下标
	 * 
	 * @param l
	 * @param r
	 * @param x
	 * @param a
	 * @return
	 */
	static int search2(int l, int r, int x, int[] a) {
		while (l <= r) {
			int mid = (l + r) / 2;
			if (x <= a[mid]) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return r;
	}
}

image-20230329191208831

标签:二分,Arrays,变形,System,param,int,查找,println,out
From: https://www.cnblogs.com/ChuenSan/p/17270043.html

相关文章

  • sql server 查找阻塞
    CREATEPROCEDURE[dbo].[sp_who_lock]ASBEGINDECLARE@spidINT,@blINT,@intTransactionCountOnEntryINT,......
  • Node.js:模块查找,引用及缓存机制
    1.Node.js的模块载入方式与机制Node.js中模块可以通过文件路径或名字获取模块的引用。模块的引用会映射到一个js文件路径,除非它是一个Node内置模块。Node的内置模块公开了......
  • Centos查找、删除僵尸进程
    CentOS1、查找僵尸进程命令:ps-A-ostat,ppid,pid,cmd|grep-e'^[Zz]'  说明:因为状态为z或者Z的进程为僵尸进程,所以我们使用grep抓取stat状态为zZ进程2、批......
  • linux在多个文件中查找指定字符串
    Linux使用grep命令检索多个文件点击查看代码grep<searchingstring><patternsearchingfile>如果我要检索当前所有md文件中的Hello关键字,可以这么用点击查看代......
  • CF(2E) Keshi in Search of AmShZ (图论,最短路,建边权值变形)
      思路: 关键是操作2的性质:随机找->找一个路径最长的点操作1,阻止建边顾名思义, 发现和最短路很想,从n到每一个点的权值嘛改变权值更新方式,边的权值为:va......
  • 整体二分总结
    整体二分总结整体二分,就是一种高效离线处理可二分答案的询问的方法,可以代替例如树套树这种高级数据结构。例题:1.P1527[国家集训队]矩阵乘法题意:多次询问,求子矩阵第\(k......
  • 二分法
    关于二分法:二分法使用要求待查找的数据集必须有序二分法的缺陷针对开头结尾的数据查找效率很低常见算法的原理以及伪代码二分法、冒泡、快拍、插入、堆排、桶排、数......
  • 用 Go 剑指 Offer 04. 二维数组中的查找
    在一个n*m的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数......
  • 2023.3.28 【模板】KM算法 | 二分图最大权完美匹配
    2023.3.28【模板】KM算法|二分图最大权完美匹配题目概述给定一张二分图,左右部均有\(n\)个点,共有\(m\)条带权边,且保证有完美匹配。求一种完美匹配的方案,使得最终......
  • LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周末是LeetCode第338场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题......