//折半查找法,要求有序序列,默认由小到大 #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; }
分享标题:折半查找法
标题来源:https://www.cdcxhl.com/article12/jhdegc.html
成都网站建设公司_创新互联,为您提供网站策划、定制开发、做网站、Google、App开发、自适应网站
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联