折半查找算法 ，接下来我们就来聊聊关于什么是编程二分查找算法 二分查找或折半查找算法?以下内容大家不妨参考一二希望能帮到您!
什么是编程二分查找算法 二分查找或折半查找算法
折半查找算法
二分法查找算法又叫折半查找。其思想是将已排好序的数列依次存入数组，设查找数值为X，用指针bot指向数列最左端位置（最小值），指针top指向数列最右端位置（最大值），取bot和top的中间值mid指向数列中间，如图所示：
1(bot) 2 3 4 5 6……….. 50(mid) ………75……. 100(top)
当top>bot时，比较查找X与a[mid]，有3种可能：
（1）若X = a[mid]，则表示找到，退出比较查找
（2）若X < a[mid]，则选择前半段继续比较查找，bot不变，top变成mid-1
（3）若X > a[mid]，则选择后半段继续比较查找，bot变成mid 1，top不变
结束过程有两种：一种是找到了X = a[mid]；另一种是没找到，即top < bot
折半查找算法实现如下：
1、使用递归算法：
#include "iostream"
#include "stdio.h"
#include "stdlib.h"
#define Max 10001
using namespace std;
int key;
int a1[5]={1,2,3,4,5};
int s1(int bot,int top){
int mid;
if(top>=bot){
mid=(top bot)/2;//取中间值
if(key==a1[mid]){
cout<<mid<<endl;
return 0;
}else if(key<a1[mid]){//如果x小于中间值，则取前半段
s1(bot,mid-1);
}else{
s1(mid 1,top);//如果x大于中间值，则取后半段
}
}else{
printf("-1\n");
return 0;
}
}
int main()
{
cin>>key;
s1(1,5);
return 0;
}
2、使用非递归算法
#include <iostream>
#include <cstdlib>
#define MAXN 10001
using namespace std;
int key2,top,bot,mid;
int a2[5] = {1,2,3,4,5};
void s2(){
top = 5;
bot = 1;
while(bot <= top){
mid = (bot top)/2;
if(key2 == a2[mid]){//如果正好找到
cout<<mid<<endl;
exit(0);
}else if(key2 < a2[mid]){//选择左半段
top = mid-1;
}else{
bot = mid 1; //选择右半段
}
}
cout<<-1<<endl;
}
