close
#include <iostream>
using namespace std;
//binary search
int binarysearch(int A[],int x,int n){
int lower=1;//陣列第一個
int upper=n;//陣列最後的個數
int mid;
while(lower<=upper) //左邊索引位置小於右邊的索引位置
{
mid=(lower+upper)/2; //設中間位置
if(x>A[mid]) // lower-------|----x----upper
lower=mid+1;// mid
// 所以 lower要MID+1
// ---------|--lower-------upper
// mid
else if(x<A[mid])
upper=mid-1; //概念類似上面
else
return mid;//傳回中間值
}
return -1; //陣列裡找不到值
}
int main(){
int A[]={1,3,5,8,9,10,15,19,20,21,23,26,30}; //可以用vector 自行輸入動態陣列元素
int n,mid,x,ans; //x為欲找的值
cout<<"輸入想收尋的值:";
cin>>x;
cout<<endl;
ans=binarysearch(A,x,sizeof(A)/sizeof(A[0])); //所佔用的空間:A=4*13=52, 除以A[0]=4; ---->因為A[0]為第一個陣列,所以不會消失
if(ans<0) //return -1;
{
cout<<"找不到"<<x;
}
else
{
cout<<"在第"<<ans+1<<"筆發現"<<x<<endl; //ans 為在第幾項發現 但陣列從0開始 所以要多+1
}
system("pause");
return 0;
}
全站熱搜
留言列表
