アルゴリズム第二章実践報告
3899 ワード
1.実践テーマ
二分検索を用いてxの下付き文字を探し出す.
2.問題の説明
n値(1<=n<=1000)、n個の非降順配列の整数および検索する数xを入力し、二分検索アルゴリズムを用いてxを検索し、xが存在する下付き(0~n-1)および比較回数を出力する.xが存在しない場合、出力-1と比較回数.
入力形式:
合計3行入力:最初の行はn値です.2行目はn個の整数である.3行目はx値です.
出力フォーマット:
xが存在する下付き(0~n-1)および比較回数を出力する.xが存在しない場合、出力-1と比較回数.
サンプルを入力:
出力サンプル:
二分検索を用いてxの下付き文字を探し出す.
2.問題の説明
n値(1<=n<=1000)、n個の非降順配列の整数および検索する数xを入力し、二分検索アルゴリズムを用いてxを検索し、xが存在する下付き(0~n-1)および比較回数を出力する.xが存在しない場合、出力-1と比較回数.
入力形式:
合計3行入力:最初の行はn値です.2行目はn個の整数である.3行目はx値です.
出力フォーマット:
xが存在する下付き(0~n-1)および比較回数を出力する.xが存在しない場合、出力-1と比較回数.
サンプルを入力:
4
1 2 3 4
1
出力サンプル:
0
2
3. #include
using namespace std;
int Search(int a[], int &x, int n,int &z){
int l=0; int r=n-1;
z=0;
while (l<=r){
z++;
int m=(l+r)/2;
if(x==a[m])
{
return m;
}
if(x>a[m])
{
l=m+1;
}
else
r=m-1;
}
return -1;
}
int main(){
int a[10000], n, x,z;
cin>>n;
for(int i=0;i){
cin>>a[i];
}
cin>>x;
int count=Search(a,x,n,z);
cout<endl;
cout<<z;
return 0;
}
4.
for ， o（n）， O(1)。
5. （ ）
， x ， 。