折半查找算法

二分法查找算法又叫折半查找。其思想是将已排好序的数列依次存入数组，设查找数值为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 10001using 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;}