二分区间

 

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<math.h>
 5 using namespace std;
 6 int a[1000010], n,m;
 7 int main()
 8 {
 9     cin >> n>>m;
10     for (int i = 1; i <= n; i++)
11         cin >> a[i];
12     while (m--)
13     {
14         int q, l = 1, r = n;
15         cin >> q;
16         while (l < r)
17         {
18             int mid = (l + r) >> 1;
19             if (a[mid] >= q)   r = mid;
20             else    l = mid + 1;
21         }
22         if (a[l] != q)
23         {
24             cout << "-1 -1" << endl;
25             continue;
26         }
27         else
28         {
29             cout << l - 1<<" ";
30         }
31 
32         l = 1, r = n;
33         while (l < r)
34         {
35             int mid = (l + r + 1) >> 1;
36             if (q >= a[mid])   l = mid ;
37             else
38             {
39                 r = mid - 1;
40             }
41         }
42         cout << l - 1 << endl;
43     }
44     return 0;
45 }

View Code

 

浮点数二分

求数的三次方根

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<math.h>
 5 using namespace std;
 6 int a[1000010],  m;
 7 int main()
 8 {
 9     double n;
10     cin >> n;
11     double l = -100.00, r = 100.00;
12     while (fabs(l - r) > 1e-9)
13     {
14         double mid = (l + r) / 2.0;
15         if (mid * mid * mid >= n)  r = mid;
16         else
17         {
18             l = mid;
19         }
20     }
21     printf("%.6lf", l);
22     return 0;
23 }

View Code