//折半查找法,要求有序序列,默认由小到大
#include <iostream>
using namespace std;
//普通方法
int BinSearch2(int *searchTable,int key,int len)
{
// 最低位置索引low、最高位置索引high、中间位置索引mid
// 中间位置的可能情况
// len为奇数时,mid 为正中间位置 mid的左侧和右侧用于同样数目的元素
// len为偶数时,mid为正中间往左的那一个元素 正中间为小数,正中间往左的那一个位置才是(Low+High)/2
// low与high的关系
// 正常情况下low<high
// low==high时,仅剩下最后一个需要判断的元素,此元素可能与key相同,也可能不同
// low>high 未找到与key相同的元素
int low=0;
int high=len-1;
int mid;
while(low<=high){
mid=(low+high)/2;
//找到与key相等的一个元素位置
if(searchTable[mid]==key)
return mid;
if (searchTable[mid]>key)
high=mid-1;
else
low=mid+1;
}
return -1;
}
//递归方法
int BinSearch3(int *searchTable,int key,int low,int high)
{
if(low>high)
return 0;//查找失败
int mid=(low+high)/2;
if(searchTable[mid]==key)
return mid;//查找成功
if(searchTable[mid]>key)
return BinSearch3(searchTable,key,low,mid-1);//左查找
else
return BinSearch3(searchTable,key,mid+1,high);//右查找
}
int main(int argc, char *argv[])
{
int Array[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
cout<<"3的位置是:"<<BinSearch2(Array,8,15)<<endl;
cout<<"3的位置是:"<<BinSearch3(Array,8,1,15)<<endl;
return 0;
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。