PTA-半値検索
半角検索
タイトル:厳密な増分数列を与え、関数
ここで、Tは秩序テーブルであり、kは検索された値である.審判試験プログラムのサンプル:
入力形式:
最初の行には整数nが入力され、順序テーブルの要素数を表し、次の行にはnの数値が入力され、テーブル内の要素値の順になります.次に、検索する値を入力します.
出力フォーマット:
この値をテーブル内の位置に出力し、見つからない場合は「NOT FOUND」を出力します.
サンプル1を入力:
5 1 3 5 7 9 7
出力サンプル1:
4
入力サンプル2:
5 1 3 5 7 9 10
出力サンプル2:
NOT FOUND
タイトル:厳密な増分数列を与え、関数
int Search_Bin(SSTable T, KeyType k)
はkの数列における位置を二分的に検索するために使用される.関数インタフェースの定義:int Search_Bin(SSTable T, KeyType k)
ここで、Tは秩序テーブルであり、kは検索された値である.審判試験プログラムのサンプル:
#include
using namespace std;
#define MAXSIZE 50
typedef int KeyType;
typedef struct
{ KeyType key;
} ElemType;
typedef struct
{ ElemType *R;
int length;
} SSTable;
void Create(SSTable &T)
{ int i;
T.R=new ElemType[MAXSIZE+1];
cin>>T.length;
for(i=1;i<=T.length;i++)
cin>>T.R[i].key;
}
int Search_Bin(SSTable T, KeyType k);
int main ()
{ SSTable T; KeyType k;
Create(T);
cin>>k;
int pos=Search_Bin(T,k);
if(pos==0) cout<
入力形式:
最初の行には整数nが入力され、順序テーブルの要素数を表し、次の行にはnの数値が入力され、テーブル内の要素値の順になります.次に、検索する値を入力します.
出力フォーマット:
この値をテーブル内の位置に出力し、見つからない場合は「NOT FOUND」を出力します.
サンプル1を入力:
5 1 3 5 7 9 7
出力サンプル1:
4
入力サンプル2:
5 1 3 5 7 9 10
出力サンプル2:
NOT FOUND
int Search_Bin(SSTable T, KeyType k)
{
int low, high, mid;
low = 1;
high = T.length;
while(low <= high)
{
mid = (low + high) / 2;
if (k == T.R[mid].key)
return mid;
else if (k < T.R[mid].key)
high = mid - 1;
else
low = mid + 1;
}
return 0;
}