二分查找的详细讨论

admin

在一个有序的表里进行查找的话没有必要使用顺序查找，比如在数组（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

二分查找的思路很简单，但是编程实现中还是会有很多的细节，现在思考几个问题，就以上面那个在（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

1. /*
   
2. 几种二分方法整理
   
3. 元素可以重复
   
4. */
   
5. 
   
6. //lower_bound(num, num+size, x)-num:大于等于x的第一个数的下标
   
7. //upper_bound(num, num+size, x)-num:大于x的第一个数的下标
   
8. 
   
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. }
    
25. 
    
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. }
    
42. 
    
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. }
    
55. 
    
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. }
    
68. 
    
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. }
    
81. 
    
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

还有一种查找是在实数域中查找，比如求根号2，精确到小数点后3位。实数是不好直接判断相等的，我们一般在循环里面加上B标记，当abs(L-R)<=EPS的时候，B标记置位，不再继续查找，请看程序。

admin

经典训练题：

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