検索アルゴリズム-二分検索
1599 ワード
テーブル内の要素が整列していると仮定し、テーブルの中間位置のキーワードを必要なキーワードと比較して等しくすると成功し、そうでなければ前後の2つのサブテーブルに分けられ、必要な値が中間要素より大きい場合は後半で検索し、そうでなければ前半で検索します.クエリーが結果になるまで、上記の手順を繰り返します.
利点:比較回数が少なく、スピードが速い
欠点:調査対象テーブルが整列テーブルであることが要求されます.
時間複雑度:O(h)=O(log 2 n)
c/c++コード実装:
方法1:ループ
このコードはmidのオーバーフロー問題のような多くの問題に気づいて、とても注意しています.
中間だけを判断するのではなく、頭の尾を判断することもあります.これにより効率が向上する.
方法2:再帰
利点:比較回数が少なく、スピードが速い
欠点:調査対象テーブルが整列テーブルであることが要求されます.
時間複雑度:O(h)=O(log 2 n)
c/c++コード実装:
方法1:ループ
int binsearch(SeqList *R，int n,KeyType K)
{
int low=0;
int higt=n-1;
int mid;
while(low<=high){
if(K==R[low].key)
return low;
if(K==R[high].key)
return high;
mid=low+(high-low)/2;
/* (low+high)/2
( low+high ，
， /2 ， low+((high-low)/2)
*/
if(K==R[mid].key)
return mid;
if(K>R[mid].key){
low=mid+1;
}
else
high=mid-1;
}
if(low>high)
return -1;
}このコードはmidのオーバーフロー問題のような多くの問題に気づいて、とても注意しています.
中間だけを判断するのではなく、頭の尾を判断することもあります.これにより効率が向上する.
方法2:再帰
#include
using namespace std;
int a[10]={1,2,3,4,5,6,7,8,9,10};
int k;
int binsearch(int low, int high){
int mid=low+(high-low)/2;
if(low>high)
return -1;
if(a[low]==k)
return low;
else if(a[high]==k)
return high;
else if(a[mid]==k)
return mid;
else{
if(k>=a[mid])
binsearch(mid+1, high);
else
binsearch(low, mid-1);
}
}
int main(){
cin>>k;
cout<