ITPub博客

首页 > 应用开发 > IT综合 > 二分查找算法

二分查找算法

原创 IT综合 作者:Diy_os 时间:2015-12-08 16:05:57 0 删除 编辑
关于二分法查找,也经常称折半查找,思想就是“分而治之”,网上有很多资料,给出维基百科上的链接(https://zh.wikipedia.org/wiki/%E6%8A%98%E5%8D%8A%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95http://www.codecodex.com/wiki/Binary_search),本文不作赘述。下面给出二分查找的非递归和递归的算法。

点击(此处)折叠或打开

  1. #include<iostream>
  2. using namespace std;
  3. int search(int *, int, int);
  4. int searchfdg(int *, int, int, int);
  5. int search(int *arra, int key, int high) {
  6.     int low = 0;
  7.     while (low <= high)
  8.     {
  9.         int mid = (low + high) / 2;
  10.           if (arra[mid] == key) {
  11.             return mid;
  12.          }else if (arra[mid] > key) {
  13.             high = mid - 1;
  14.          }else
  15.             low = mid + 1;
  16.     }
  17.     cout << "元素不存在!";
  18.         return -1;
  19. }
  20.   
  21. int searchfdg(int *arra, int key,int low,int high) {
  22.       
  23.         if (low <= high)
  24.         {
  25.             int mid = (low + high) / 2;
  26.             if (key == arra[mid]){
  27.                 return mid;
  28.             }
  29.             else if (key < arra[mid]) {
  30.                 return searchfdg(arra, key, low, mid - 1);
  31.             }else if (key > arra[mid])
  32.                 low = mid + 1;
  33.                 return searchfdg(arra, key, mid+1,high);
  34.         }
  35.         else
  36.             cout << "元素不存在!";
  37.             return -1;
  38.     }
  39. int main() {
  40.     int arra[] = {3,5,9,14,17,23,29,33,37 };
  41.     int size = sizeof(arra) / sizeof(int);
  42.     cout << "非递归查找的元素在数组中的位置是:" << endl;
  43.     cout << search(arra, 33, size-1) << endl;
  44.     cout << "递归查找的元素在数组中的位置是:" << endl;
  45.     cout << searchfdg(arra, 33, 0,size-1) << endl; //注意此时的low和high的值
  46.   
  47. }
运行结果:

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1868404/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2014-12-11

  • 博文量
    159
  • 访问量
    982609