何謂折半查找，舉個(gè)例子很快就可以明白，給你了9個(gè)數(shù) 1 2 3 4 5 6 7 8 9 讓你去找2在哪里，這時(shí)候你肯定會(huì)說(shuō)這太簡(jiǎn)單了，但是計(jì)算機(jī)就沒(méi)那么強(qiáng)了，它得拿著2和這9個(gè)數(shù)一個(gè)一個(gè)的比較，2在前面還好比較的次數(shù)比較小，但是如果讓你找6在哪呢，需要比較的次數(shù)就多了，可能你覺(jué)得多這一次兩次沒(méi)什么差別，但是如果1到10000個(gè)數(shù)讓你找呢，這時(shí)候折半查找的優(yōu)勢(shì)就顯現(xiàn)出來(lái)了。我們先看2在不在1-5里面也就是前半段，如果在前半段，我們直接不和后邊的數(shù)進(jìn)行比較，我們確定2在1到5里面之后，我們?cè)儆妙?lèi)似的辦法再去掉一半，看2在不在1到3面里，如果不在我們?nèi)?到5里找，如此下去直到找到為止，我們會(huì)發(fā)現(xiàn)計(jì)算機(jī)最擅長(zhǎng)干的事就是迭代，而優(yōu)秀的算法就是讓計(jì)算機(jī)迭代的次數(shù)少一點(diǎn)。c++用代碼實(shí)現(xiàn)如下

#include<iostream> using namespace std; int main() {const int n=10;int i,number,top,bott,mid,loca,a[n];//mid用bott和top表示，方便迭代。bool flag=true,sign;//設(shè)置布爾變量即標(biāo)志位。char c;cout<<"enter data:"<<endl;cin>>a[0];i=1;while(i<n){cin>>a[i];if(a[i]>=a[i-1])i++;elsecout<<"enter this data again:";//輸入已經(jīng)排好序的數(shù)列，也可以加上冒泡排序自動(dòng)排序}cout<<endl;for(i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;while(flag){cout<<"input number of to look for:";cin>>number;sign=false;top=0;bott=n-1;if((number<a[0])||(number>a[n-1]))loca=-1;while((!sign)&&(top<=bott)){mid=(bott+top)/2;if(number==a[mid]){loca=mid;cout<<"find"<<number<<",its position is"<<loca+1<<endl;sign=true;}else if(number<a[mid])bott=mid-1;//舍去后一半elsetop=mid+1;}if(!sign||loca==-1)cout<<number<<"has not found"<<endl;cout<<"continue or not";cin>>c;if(c=='n'||c=='N')flag=false;}return 0; }

輸入十個(gè)已經(jīng)排好序的數(shù)，然后進(jìn)行查找。

總結(jié)

以上是生活随笔為你收集整理的c++折半查找算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。