1. 首页
  2. IT资讯

二分查找算法

关于二分法查找,也经常称折半查找,思想就是“分而治之”,网上有很多资料,给出维基百科上的链接(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, size1) << endl;
  44.     cout << “递归查找的元素在数组中的位置是:” << endl;
  45.     cout << searchfdg(arra, 33, 0,size1) << endl; //注意此时的low和high的值
  46.   
  47. }

运行结果:
二分查找算法

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

主题测试文章,只做测试使用。发布者:℅傍ㄖ免沦陷dε鬼,转转请注明出处:http://www.cxybcw.com/191819.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code