华师一附中OI组

标题: 二分查找的详细讨论 [打印本页]
作者: admin    时间: 2018-4-21 18:33
标题: 二分查找的详细讨论
在一个有序的表里进行查找的话没有必要使用顺序查找，比如在数组（1,3,5,7,9,11,13,15,17,19）十个数中查找数X=11，我们可以使用二分查找：
初始设起点L=1，终点R=10，没有找到标记B=1。
1、枚举中间位置，M=（L+R）/2=5。这个数字 A（M）=9，9<11,说明要找的数字X在M的右边，那么更新查找起点L=M+1=6，R不变，（想想为什么是M+1）
2、枚举中间位置，M=（L+R）/2=8。A（8）=15，比X小，说明要找的数字X在M的左边，更新查找的终点R=M-1=7，L不变，
3、枚举中间位置，M=（L+R）/2=6。这次找到了A（6）=11。退出查找过程。
这个程序有两种实现，一种是用递归，一种是用迭代。代码如下：
  1. ///递归的二分查找
  2. int bs(int x,int l,int r)
  3. {
  4.     if (r<l) return -1;
  5.     else
  6.     {
  7.         int m=(l+r)/2;   ///m=l+(r-l)/2;
  8.         if (a[m]==x) return m;
  9.         else if (a[m]>x) return bs(x,l,m-1);  ///小了就找左边
  10.         else if (a[m]<x) return bs(x,m+1,r);///大了就找右边
  11.     }
  12. }
复制代码
  1. ///迭代的二分查找
  2. int bs2(int x,int l,int r)
  3. {
  4.     int m;
  5.     bool b=true;///未找到标记
  6.     while (l<=r && b)
  7.     {
  8.         m=(l+r)/2;
  9.         if (a[m]==x) b=false; ///找到了
  10.         else if (a[m]>x) r=m-1;///小了就找左边
  11.         else l=m+1;///大了就找右边
  12.     }
  13.     if (!b) return m;
  14.     else return -1;
  15. }
复制代码





作者: admin    时间: 2018-7-15 14:23
二分查找的思路很简单，但是编程实现中还是会有很多的细节，现在思考几个问题，就以上面那个在（1,3,5,7,9,11,13,15,17,19）十个数中查找数X为例，假设L=1 R=10。
1、设X=11，找到了在第6位，查找完毕后L和R的值分别是多少？
2、设X=10，找不到X，退出循环的时候L和R的值分别是多少？
3、B标记到底有没有必要？



自然数域里的查找是精确的，找到找不到是明确，但是实数范围内的查找由于精度的问题，需要做特殊的处理，比如我们要求根号2，设为X，那么X=1.414吗？当要求的精度只有小数点后三位的时候的确是这样的，所以我们可以在程序里面加上一个判断精度是否达到的语句，只要精度达到就可以退出，而不是一定要求a(m)==X。



作者: admin    时间: 2018-9-16 21:37
  1. /*
  2. 几种二分方法整理
  3. 元素可以重复
  4. */

  6. //lower_bound(num, num+size, x)-num:大于等于x的第一个数的下标
  7. //upper_bound(num, num+size, x)-num:大于x的第一个数的下标

  9. //1.求等于x的最小的index，不存在返回-1
  10. int binary (int *num, int start, int end, int x) {
  11.         int l = start, r = end, ans=-1;
  12.         while(l <= r) {
  13.                 int mid = (l+r) >> 1;
  14.                 if(num[mid] == x) {
  15.                         ans = mid;
  16.                         r = mid - 1;
  17.                 }
  18.                 else if(num[mid] > x)
  19.                         r = mid - 1;
  20.                 else
  21.                         l = mid + 1;
  22.         }
  23.         return ans;
  24. }

  26. //2.求等于x的最大的index，不存在返回-1
  27. int binary (int *num, int start, int end, int x) {
  28.         int l = start, r = end, ans=-1;
  29.         while(l <= r) {
  30.                 int mid = (l+r) >> 1;
  31.                 if(num[mid] == x) {
  32.                         ans = mid;
  33.                         l = mid + 1;
  34.                 }
  35.                 else if(num[mid] > x)
  36.                         r = mid - 1;
  37.                 else
  38.                         l = mid + 1;
  39.         }
  40.         return ans;
  41. }

  43. //3.求小于x的最大的index
  44. int binary (int *num, int start, int end, int x) {
  45.         int l = start, r = end;
  46.         while(l <= r) {
  47.                 int mid = (l+r) >> 1;
  48.                 if(num[mid] >= x)
  49.                         r = mid - 1;
  50.                 else
  51.                         l = mid + 1;
  52.         }
  53.         return r;
  54. }

  56. //4.求大于x的最小的index
  57. int binary (int *num, int start, int end, int x) {
  58.         int l = start, r = end;
  59.         while(l <= r) {
  60.                 int mid = (l+r) >> 1;
  61.                 if(num[mid] <= x)
  62.                         l = mid + 1;
  63.                 else
  64.                         r = mid - 1;
  65.         }
  66.         return l;
  67. }

  69. //5.求大于等于x的最小的index
  70. int binary (int *num, int start, int end, int x) {
  71.         int l = start, r = end;
  72.         while(l <= r) {
  73.                 int mid = (l+r) >> 1;
  74.                 if(num[mid] >= x)
  75.                         r = mid - 1;
  76.                 else
  77.                         l = mid + 1;
  78.         }
  79.         return l;
  80. }

  82. //6.求小于等于x的最大的index
  83. int binary (int *num, int start, int end, int x) {
  84.         int l = start, r = end;
  85.         while(l <= r) {
  86.                 int mid = (l+r) >> 1;
  87.                 if(num[mid] <= x)
  88.                         l = mid + 1;
  89.                 else
  90.                         r = mid - 1;
  91.         }
  92.         return r;
  93. }
复制代码
作者: admin    时间: 2020-7-17 10:35
还有一种查找是在实数域中查找，比如求根号2，精确到小数点后3位。实数是不好直接判断相等的，我们一般在循环里面加上B标记，当abs(L-R)<=EPS的时候，B标记置位，不再继续查找，请看程序。
作者: admin    时间: 2020-7-17 10:38
经典训练题：

P1024   一元三次方程求解 https://www.luogu.org/problemnew/show/P1024 我的解法参考 http://www.hsyit.cn/forum.php?mo ... 5793&highlight=1024
P1163   银行贷款 https://www.luogu.org/problemnew/show/P1163 我的解法参考 http://www.hsyit.cn/forum.php?mo ... 5796&highlight=1163



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2