devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二分查找算法_在一个有序表中进行二分查找操作,要求查找元素x,统计查找过程中需要比较的次数。

作者：知新_RL | 2024-05-26 01:08:31

赞

踩

在一个有序表中进行二分查找操作,要求查找元素x,统计查找过程中需要比较的次数。

二分查找算法讲解

枚举查找也就是顺序查找。

实现原理就是逐个比较 a[0:n-1] 中的元素，直到找出元素 x 或搜索遍整个数组后确定 x 不在其中，或者说符合要求的元素在不在数组中。

最坏的情况下需要比较 N 次，时间复杂度是 O(n) 线性阶。

二分查找也就是折半查找。折半查找是将 N 个元素分成大致相同的两部分。选取中间元素与查找的元素比较，或者与查找条件相比较，找到或者说找到下一次查找的半区。每次都将范围缩小至1/2​ 所以时间复杂度是 O(log2n），但是二分查找的前提是有序的，一般是从小到大排列。且一般用于查<=x的max值或>=x的min值。

折半查找的基本思想：

在有序表中（low,high,low<=high），取中间记录即 [(high+low)/2] 作为比较对象。

  • 若给定值与中间记录的关键码相等，则查找成功
  • 若给定值小于中间记录的关键码，则在中间记录的左半区继续查找
  • 若给定值大于中间记录的关键码，则在中间记录的右半区继续查找

不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

二分查找的特征：

  1. 答案具有单调性；
  2. 二分答案的问题往往有固定的问法，比如：令最大值最小（最小值最大），求满足条件的最大（小）值等。

折半查找一般过程：

 Step 1:
 假设存在一有序数组，要找14：
数据[ 7   14  18  21  23  29  31  35   38   42   46   49  52 ]
         ↑                                                                      ↑
     low=0                                                             high=12
                            mid=(low+high)/2=(0+12)/2=6
                            [mid]=31>14 所以选择左半部分
 此时令low不变，high=mid=6
 Step 2:
数据[ 7   14  18  21  23  29  31  35   38   42   46   49  52 ]
        ↑                                 ↑
   low=0                         high=6
            mid=(low+high)/2=(0+6)/2=3
            [mid]=21>14 所以选择左半部分
 此时令low不变，high=mid=3
 Step 3:
数据[ 7   14  18  21  23  29  31  35   38   42   46   49  52 ]
        ↑                ↑
   low=0         high=3
            mid=(low+high)/2=(0+3)/2=1
            [mid]=14=14  找到答案，返回下标。

整数二分法常用算法模板： 

  1. // 在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
  2. while (low < high) {
  3.  
  4.   int mid = (low + high) / 2;
  5.  
  6.   if (a[mid] >= x)
  7.       high= mid; 
  8.  
  9.   else 
  10.       low = mid+1;
  11. }
  12. // 在单调递减序列a中查找>=x的数中最小的一个（即x或x的后继）
  13.  while (low < high) {
  14.  
  15.   int mid = (low + high+1) / 2;
  16.  
  17.   if (a[mid] >= x)
  18.       low= mid; 
  19.  
  20.   else 
  21.       high = mid-1;
  22. }
  23. // 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
  24. while (low < high) {
  25.  
  26.   int mid = (low + high + 1) / 2;
  27.  
  28.   if (a[mid] <= x) 
  29.       low = mid;
  30.  
  31.   else 
  32.       high = mid-1;
  33.  
  34. }
  35. //在单调递减序列a中查找<=x的数中最大的一个（即x或x的前驱）
  36. while (low < high) {
  37.  
  38.   int mid = (low + high) / 2;
  39.  
  40.   if (a[mid] >= x)
  41.       low= mid+1; 
  42.  
  43.   else 
  44.       high = mid;
  45. }
  46. //查找x
  47. while (low < high) {
  48.  
  49.   int mid = (low + high) / 2;
  50.  
  51.   if (a[mid] >= x)
  52.       high= mid; 
  53.  
  54.   else 
  55.       low = mid;
  56. }

分巧克力

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
 1. 形状是正方形，边长是整数;
 2. 大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述:
 第一行包含两个整数 N,K (1≤N,K≤10^5）。
 以下 N 行每行包含两个整数 Hi Wi (1≤Hi,Wi≤10^5)。
 输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述:
 输出切出的正方形巧克力最大可能的边长。

输入样例
2 10
6 5
5 6
 输出样例 
2

运行限制：

最大运行时间：1s
最大运行内存：256M
注意：
1. 请严格按要求输出，不要画蛇添足地打印类似：“请您输入…”的多余内容。
2. 不要调用依赖于编译环境或操作系统的特殊函数。
3. 所有依赖的函数必须明确地在源文件中
4. 不能通过工程设置而省略常用头文件。

在判断边长是否满足条件时：求一块长方形（h * w）最多被分成的正方形（len * len）巧克力个数。-----》（h*w）/（len*len) -----》 (h/len)*(w/len)

用在单调递增序列 a 中查找 <=x 的数中最大的一个（即 x 或 x 的前驱）即可，这里的条件可以看成是 <=x ，我们将其换成验证即可。

代码如下：

  1. import java.util.Scanner;
  2.  
  3. import static java.lang.Integer.max;
  4.  
  5. public class Main {
  6.  
  7.   static int n, k;
  8.  
  9.   static int h[] = new int[100005];
  10.  
  11.   static int w[] = new int[100005];
  12.  
  13.   static boolean pd(int l) {//判断是否满足k个人分
  14.       int sum = 0;
  15.       for (int i = 0; i < n; i++) {
  16.           sum += (h[i] / l) * (w[i] / l);//求n块巧克力一共最多可以分多少小块
  17.           if (sum >= k) {//可以分
  18.               return true;
  19.           }
  20.       }
  21.       return false;
  22.   }
  23.  
  24.   public static void main(String[] args) {
  25.  
  26.       Scanner in = new Scanner(System.in);
  27.  
  28.       n = in.nextInt();
  29.  
  30.       k = in.nextInt();
  31.  
  32.       //找到二分查找的上界
  33.       int high = 0;
  34.  
  35.       for (int i = 1; i <= n; i++) {
  36.           h[i] = in.nextInt();
  37.  
  38.           w[i] = in.nextInt();
  39.  
  40.           high = max(high, h[i]);
  41.           high = max(high, w[i]);
  42.       }
  43.  
  44.       // 二分下届由题意可得至少为1
  45.       int low = 1;
  46.  
  47.  
  48.       // 由于本题目就是求符合要求的Mid 值所以要将mid定义在二分查找外边
  49.  
  50.       int mid = 0;
  51.  
  52.       while (low < high) {
  53.  
  54.            mid = (low + high) / 2;
  55.  
  56.           if (pd(mid))
  57.               low = mid+1;
  58.  
  59.           else
  60.               high = mid;
  61.  
  62.       }
  63.  
  64.       //因为low=high所以输出哪一个都一样
  65.  
  66.       System.out.println(low);
  67.  
  68.   }
  69. }

 M 次方根

小A最近在学高等数学，他发现了一道题，求三次根号下27。现在已知，小 A 开始计算，1 的三次方得1，2 的三次方得 8，3 的三次方得 27，然后他很高兴的填上了 3。
 接着他要求 5 次根号下 164。然后他开始 1 的三次方得 1，2 的三次方得 8，3 的三次方得27...
 直到他算到了秃头，也没有找到答案。
 这时一旁的小 B 看不下去了，说这题答案又不是个整数。小 A 震惊，原来如此。作为程序高手的小 A，打算设计一个程序用于求解 M 次跟下N的值。
 但是由于要考虑精度范围，答案必须要保留 7 位小数，连三次根号下 27 都要掰手指的小 A 又怎么会设计呢。请你帮小 A 设计一个程序用于求解 M 次根号 N。
数据范围：
1<= N <= 10^5 
1<= M <= 100
且 M<N

输入描述:
 第一行输入整数 N 和 M，数据间用空格隔开。

输出描述:
 输出一个整数，并保留 7 位小数。

输入样例：
 27 3
输出样例：
3.000000

运行限制：

最大运行时间：1s
最大运行内存: 256M
 注意：
1. 请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
2. 不要调用依赖于编译环境或操作系统的特殊函数。
3. 所有依赖的函数必须明确地在源文件中。
4. 不能通过工程设置而省略常用头文件。

其实二分法还是可以用于实数。

根据前面的知识，要找到一个具有单调性的数列，去二分。这个题的关键是去二分什么，这里可以二分的是 a^M 中的 a。

这里有两个用于处理实数二分的代码模板，都可以，二选一即可：

  1. //令eps 为小于题目精度一个数即可。
  2.  
  3. //比如题目说保留4位小数，0.0001 这种的。那么eps 就可以设置为五位小数的任意一个数 0.00001- 0.00009 等等都可以。一般为了保证精度我们选取精度 /100 的那个小数，即设置  eps= 0.0001/100 =1e-6。
  4.  
  5. while (l + eps < r) {
  6.   double mid = (l + r) / 2;
  7.  
  8.   if (pd(mid)) 
  9.       r = mid; 
  10.   else 
  11.       l = mid;
  12. }
  13.  
  14. //模板2： 实数域二分，规定循环次数法
  15.  
  16. //通过循环一定次数达到精度要求，这个一般log2N< 精度即可。N为循环次数，在不超过时间复杂度的情况下，可以选择给N乘一个系数使得精度更高。
  17.  
  18. for (int i = 0; i < 100; i++) {
  19.  
  20.   double mid = (l + r) / 2;
  21.   if (pd(mid)) 
  22.       r = mid; 
  23.   else 
  24.       l = mid;
  25. }

接下来考虑判定条件。关于判定条件，我们应该设计一个代码用于比较 a^m 和 N 的大小关系。

pd 成功的情况，一定是 pd 的 mid 符合条件，且小于 mid 的一定符合条件。因此我们要在大于 mid 中继续查找，找到更大的 mid。

  1. double pd(double a,int m)
  2. {
  3.     double c=1;
  4.     while(m>0)
  5.     {
  6.         c=c*a;
  7.         m--;
  8.     }
  9.     if(c>=n)
  10.         return true;
  11.     else
  12.         return false;
  13. }

代码实现：

  1. package com.company;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.  
  6.   static double n, l, r, mid;
  7.   static double eps = 1e-8;//10^(-8)
  8.  
  9.   static boolean pd(double a, int m) {
  10.       double c = 1;
  11.  
  12.       while (m > 0) {
  13.  
  14.           c = c * a;
  15.           m--;
  16.  
  17.       }
  18.       //c=a^m>=n; a>= M 次根号 N
  19.       if (c >= n)
  20.  
  21.           return true;
  22.  
  23.       else
  24.           return false;
  25.   }
  26.  
  27.   public static void main(String[] args) {
  28.  
  29.       int m;
  30.       Scanner in =new Scanner(System.in);
  31.       n=in.nextDouble();
  32.       m=in.nextInt();
  33. //设置二分边界
  34.  
  35.       l = 0;
  36.       r = n;
  37.  
  38. //实数二分
  39.       while (l + eps < r) {//如果不加1，eps和r永远不能结束程序，跑不出来
  40.           double mid = (l + r) / 2;
  41.  
  42.           if (pd(mid, m))
  43.               r = mid;
  44.  
  45.           else
  46.               l = mid;
  47.       }
  48.  
  49.       System.out.println(String.format("%.7f",l));
  50.   /*
  51.    关于string.format 的应用
  52.   double num = 123.4567899;
  53.   System.out.print(String.format("%f %n", num)); // 123.456790
  54.   System.out.print(String.format("%a %n", num)); // 0x1.edd3c0bb46929p6
  55.   System.out.print(String.format("%g %n", num)); // 123.457
  56.   可用标识：
  57.         -，在最小宽度内左对齐,不可以与0标识一起使用。
  58.         0，若内容长度不足最小宽度，则在左边用0来填充。
  59.         #，对8进制和16进制，8进制前添加一个0,16进制前添加0x。
  60.         +，结果总包含一个+或-号。
  61.         空格，正数前加空格，负数前加-号。
  62.         ,，只用与十进制，每3位数字间用,分隔。
  63.         (，若结果为负数，则用括号括住，且不显示符号。
  64.   可用转换符：
  65.         b，布尔类型，只要实参为非false的布尔类型，均格式化为字符串true，否则为字符串false。
  66.         n，平台独立的换行符, 也可通过System.getProperty("line.separator")获取。
  67.         f，浮点数型（十进制）。显示9位有效数字，且会进行四舍五入。如99.99。
  68.         a，浮点数型（十六进制）。
  69.         e，指数类型。如9.38e+5。
  70.         g，浮点数型（比%f，%a长度短些，显示6位有效数字，且会进行四舍五入）
  71.    */
  72.  
  73.   }
  74. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/624481
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号