二分查找 - waiting...'s Blog

二分查找

waiting... posted @ 2009年3月03日 00:41 in C/C++ with tags 二分 查找 折半 , 1379 阅读

 二分查找函数：

  1. // 对于传入的以升序排列数组参数a，它以，则在下标为from和to之间查找值为num的数，找的则返回其下标；否则，返回-1
  2. int binary_search(const int a[], int from, int to, int num)
  3. {
  4.         if (from > to)
  5.                 return -1;
  6.  
  7.         int mid = (from + to) / 2;
  8.         if (a[mid] == num)
  9.                 return mid;
  10.         else if (a[mid] < num)
  11.                 return binary_search(a, mid + 1, to, num);
  12.         else
  13.                 return binary_search(a, from, mid - 1, num);
  14. }

 

完整代码： 

  1. #include <iostream>
  2. #include <ctime>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. // 设置随机整数的种子
  7. void rand_seed()
  8. {
  9.         unsigned int seed = static_cast<unsigned int>(time(NULL));
  10.         srand(seed);
  11. }
  12.  
  13. // 返回一个介于lower与upper之间的一个随机整数
  14. int randInt(int lower, int upper)
  15. {
  16.         return lower + rand() % (upper - lower + 1);
  17. }
  18.  
  19. void print(const int a[], const int length)
  20. {
  21.         for (int i = 0; i < length; i++)
  22.                 cout << a[i] << " ";
  23.         cout << endl;
  24. }
  25.  
  26. // 对于传入的以升序排列数组参数a，它以，则在下标为from和to之间查找值为num的数，找的则返回其下标；否则，返回-1
  27. int binary_search(const int a[], int from, int to, int num)
  28. {
  29.         if (from > to)
  30.                 return -1;
  31.  
  32.         int mid = (from + to) / 2;
  33.         if (a[mid] == num)
  34.                 return mid;
  35.         else if (a[mid] < num)
  36.                 return binary_search(a, mid + 1, to, num);
  37.         else
  38.                 return binary_search(a, from, mid - 1, num);
  39. }
  40.  
  41. int main()
  42. {
  43.         const int length = 20;
  44.         const int lower = 1;  // 随机数上限
  45.         const int upper = 20;  // 随机数下限
  46.         int a[length];
  47.  
  48.         rand_seed();
  49.         a[0] = 11;
  50.         for (int i = 1; i < length; i++)
  51.                 a[i] = a[i - 1] + randInt(lower, upper);
  52.  
  53.         print(a, length);
  54.  
  55.         int num;  //  待查找的数字
  56.         while (cin >> num)
  57.         {
  58.                 int temp_index = binary_search(a, 0, length, num);
  59.                 if (temp_index != -1)
  60.                         cout << "a[" << temp_index << "] = " << a[temp_index] << endl;
  61.                 else
  62.                         cout << "未找到" << endl;
  63.         }
  64.         return 0;
  65. }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee