关于二分法查找，也经常称折半查找，思想就是“分而治之”，网上有很多资料，给出维基百科上的链接（https://zh.wikipedia.org/wiki/%E6%8A%98%E5%8D%8A%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95，http://www.codecodex.com/wiki/Binary_search），本文不作赘述。下面给出二分查找的非递归和递归的算法。
运行结果：
点击(此处)折叠或打开
-
#include<iostream>
-
using namespace std;
-
int search(int *, int, int);
-
int searchfdg(int *, int, int, int);
-
int search(int *arra, int key, int high) {
-
int low = 0;
-
while (low <= high)
-
{
-
int mid = (low + high) / 2;
-
if (arra[mid] == key) {
-
return mid;
-
}else if (arra[mid] > key) {
-
high = mid - 1;
-
}else
-
low = mid + 1;
-
}
-
cout << "元素不存在！";
-
return -1;
-
}
-
-
int searchfdg(int *arra, int key,int low,int high) {
-
-
if (low <= high)
-
{
-
int mid = (low + high) / 2;
-
if (key == arra[mid]){
-
return mid;
-
}
-
else if (key < arra[mid]) {
-
return searchfdg(arra, key, low, mid - 1);
-
}else if (key > arra[mid])
-
low = mid + 1;
-
return searchfdg(arra, key, mid+1,high);
-
}
-
else
-
cout << "元素不存在！";
-
return -1;
-
}
-
int main() {
-
int arra[] = {3,5,9,14,17,23,29,33,37 };
-
int size = sizeof(arra) / sizeof(int);
-
cout << "非递归查找的元素在数组中的位置是：" << endl;
-
cout << search(arra, 33, size-1) << endl;
-
cout << "递归查找的元素在数组中的位置是：" << endl;
-
cout << searchfdg(arra, 33, 0,size-1) << endl; //注意此时的low和high的值
-
- }
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29876893/viewspace-1868404/ ，如需转载，请注明出处，否则将追究法律责任。
下一篇：
Josephus问题解决方法五（递归）
请登录后发表评论
登录
全部评论
