個人アルゴリズム復習ノート1-二分検索
2792 ワード
個人アルゴリズム復習ノート1-二分検索
二分検索の前提は、この配列が秩序化されていることであるため、1つのkey値と1つの並べ替えられたVectorコンテナを受信し、アルゴリズムは2つの変数lo,hiを使用して両端を記録し、毎回中間値を計算してkeyと比較し、kyeが中間値より小さい場合、keyは必ず中間値の左側にあるので、hi=mid-1である.逆にkey>midの場合、keyは必ず中間値の右側にあり、lo=mid+1となり、key=中間値が見つかった場合に検索が完了する.lo>hiの場合は、見つからないことを示します.-1に戻します.
このアルゴリズムの性能:配列にN個のデータがある場合、ライブラリ関数を用いた高速ソートの効率はNlogn程度であり、二分検索にはlogn時間が必要である.このアルゴリズムは全体的にNlognレベルです
二分検索の前提は、この配列が秩序化されていることであるため、1つのkey値と1つの並べ替えられたVectorコンテナを受信し、アルゴリズムは2つの変数lo,hiを使用して両端を記録し、毎回中間値を計算してkeyと比較し、kyeが中間値より小さい場合、keyは必ず中間値の左側にあるので、hi=mid-1である.逆にkey>midの場合、keyは必ず中間値の右側にあり、lo=mid+1となり、key=中間値が見つかった場合に検索が完了する.lo>hiの場合は、見つからないことを示します.-1に戻します.
このアルゴリズムの性能:配列にN個のデータがある場合、ライブラリ関数を用いた高速ソートの効率はNlogn程度であり、二分検索にはlogn時間が必要である.このアルゴリズムは全体的にNlognレベルです
#include
#include
#include
using namespace std;
int binarysearch(int key, vector<int> &a)
{
int lo=0,hi=a.size();//
while(lo<=hi)
{
int mid=lo+(hi-lo)/2;//
if(key1;
else if(key>a.at[mid])
lo=mid+1;
else
return mid;
}
return -1;
}
int main()
{
int n,key,temp;
cin>>n;
vector<int> a;
ifstream in=("1.txt");//
if(in==null)//
cout<<"flase"<else
for(int i=0;i>temp;
a.push_back(temp);}//
a.sort();//
cin>>key;
int result=binarysearch(key,a);
cout<return 0;
}