二元搜尋法

利用二元搜尋法 找出第1500位是2或3或5的倍數。
ps.其實這題目不是我本來要算的題目 = =+

想法步驟 :

1. 先寫一個函數算出是第幾位數(數學)

2. 設定mid = (頭 + 尾) / 2

3. 把mid 放到函數去，跑出來數字如果大於1500位，就表示從mid 到 尾端的一系列數字都會比1500大，就都捨去不用算了，然後設定"尾" = mid -1

4.小於的想法也是一樣，"頭" = mid +1。

5.最後用迴圈就可以跑出答案囉!!

1. /****************************************
2. Project: 運用binary serach 找出第1500個 是2或3或5的倍數
3. Aurhor:  CHEN YU YUAN
4. Language: C++
5. ****************************************/
6. #include <iostream>
7. using namespace std;
9. int U(int n)
10. {
11.         return n/2 + n/3 + n/5 - n/6 - n/10 - n/15 + n/30;
12. }
14. int main()
15. {
16.         int n = 0, a1 = 1, a2 = 3000, mid;
17.         while ( U(mid) != 1500 )
18.         {
19.                 mid = (a1+a2) / 2;
20.                 if( U(mid) > 1500)
21.                 {
22.                         cout << '#' << ++n << " 次搜尋的數字為" << U(mid) <<endl;
23.                         a2 = mid - 1;
24.                 }
25.                 else if ( U(mid) < 1500)
26.                 {
27.                         cout << '#' << ++n << " 次搜尋的數字為" << U(mid) <<endl;
28.                         a1 = mid + 1;
29.                 }
30.                 else
31.                 {
32.                         cout << "find out!!";
33.                         break;
34.                 }
35.         }
36.          cout << mid;
37. }