二分查找
2021/7/10 6:06:03
本文主要是介绍二分查找,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
整数二分
整数二分要考虑边界问题,可以将二分查找分为两种情况。
- mid = (left + right) / 2
1 left = 0; right = n - 1; 2 mid = (left + right) / 2; 3 //查找x 4 while(left < right){ 5 if(array[mid] >= x) //当前mid的值大于等于查找值,即此时查找结果在mid的左边(包括mid)——result <= mid 6 right = mid; 7 else //当前mid的值小于查找值,此时查找结果在mid的右边(不包括mid) 8 left = mid + 1; 9 }
- mid = (left + right + 1) /2
left = 0; right = n - 1; mid = (left + right + 1) / 2; while(left < right){ if(array[mid] <= x) //当mid的值小于等于查找的值,此时结果在mid的右边,所以需要让left = mid. left = mid; else right = mid - 1; }
因为这里除法的取整是向下取整,所以当left = right - 1时,mid = (left + right) / 2 = left,这时循环中若left = mid则会造成死循环,所以需要在mid赋值时使其向上取整,这样不会造成死循环且不会影响最后的结果。
例题:数的范围
给定一个按照升序排列的长度为 n 的整数数组,以及 q个查询。
对于每个查询,返回一个元素 k的起始位置和终止位置(位置从 0开始计数)。
如果数组中不存在该元素,则返回 -1 -1
。
输入格式
第一行包含整数 n和 q,表示数组长度和询问个数。
第二行包含 n个整数(均在 1∼10000范围内),表示完整数组。接下来 q行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1
。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例:
6 3 1 2 2 3 3 4 3 4 5
输出样例:
3 4 5 5 -1 -1
1 import java.io.BufferedInputStream; 2 import java.util.Scanner; 3 4 public class Main{ 5 public static void main(String[] args){ 6 Scanner scan = new Scanner(new BufferedInputStream(System.in)); 7 int n = scan.nextInt(); 8 int m = scan.nextInt(); 9 int[] q = new int[n]; 10 for(int i = 0; i < n; i++) q[i] = scan.nextInt(); 11 while(m > 0){ 12 int l = 0, r = n - 1; // l 与 r的定义需要在第一个while中,因为每次m值改变则代表一次查找的结束,需要重新定义一次l与r,若放在循环外会影响第一次以外的查找 13 int x = scan.nextInt(); 14 while(l < r){ 15 int mid = (l + r) / 2; 16 if(q[mid] >= x) r = mid; 17 else l = mid + 1; 18 } 19 if(q[l] != x) System.out.println("-1 -1"); 20 else{ //若已查找到第一个索引位置,则再进行一次查找 21 System.out.print(l + " "); 22 l = 0; r = n - 1; 23 while(l < r){ 24 int mid = (l + r + 1) / 2; 25 if(q[mid] <= x) l = mid; 26 else r = mid - 1; 27 } 28 System.out.println(l); 29 } 30 m--; 31 } 32 } 33 }
浮点数二分
浮点数二分比较简单,因为不需要考虑边界问题,直接取mid即可。
1 left = 0; right = n - 1; 2 while(l < r){ 3 double mid = (l + r) / 2; 4 if(check(mid)) r = mid; 5 else l = mid; 6 }
这篇关于二分查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南