折りたたみハーフディンディング方法:
順序付けられたテーブルで、検索範囲の中間要素値で検索するデータ値を比較すると、次の3つの状況があります。
1)見つかるデータ値が中間要素値に正確に等しい場合、中間要素値のインデックスを戻します。
2)検索するデータ値が中間要素の値よりも小さい場合は、検索範囲全体の前半を新しい検索範囲として使用し、1)等しい値が見つかるまで実行します。
3)検索するデータ値が中間要素の値よりも大きい場合、検索範囲全体の後半を新しい検索範囲として使用し、1)等しい値が見つかるまで実行します。
4)最終的に同じ値が見つからない場合、エラーメッセージが返されます。
バイナリツリーによると、中央の値はバイナリツリーの根、前半は左サブツリー、後半は右サブツリーです。ハーフファインディング検索方法の検索数は、値が配置されているレイヤーの数です。同等の確率で、およそ
log2(n+1)-1
コードコピーは次のとおりです。
//データは検索する配列、xは検索するデータ値、検索範囲の開始であり、最後は検索範囲の終わりです
//非再帰法
int bisearch(int data []、const int x、int beg、int last)
{
int mid; //中間位置
if(beg> last)
{
return -1;
}
while(beg <= last)
{
mid =(beg + last) / 2;
if(x == data [mid])
{
途中で戻ります。
}
else if(data [mid] <x)
{
beg = mid + 1;
}
else if(data [mid]> x)
{
last = mid -1;
}
}
return -1;
}
//再帰的な方法
int iterbisearch(int data []、const int x、int beg、int last)
{
int mid = -1;
mid =(beg + last) / 2;
if(x == data [mid])
{
途中で戻ります。
}
else if(x <data [mid])
{
return iterbisearch(data、x、beg、mid -1);
}
else if(x> data [mid])
{
return iterbisearch(data、x、mid + 1、last);
}
return -1;
}
//メイン関数
int _tmain(int argc、_tchar* argv [])
{
int data1 [60] = {0};
int no2search = 45;
cout << "配列は:" << endl;
int siz = sizeof(data1)/sizeof(int);
for(int i = 0; i <siz; i ++)
{
data1 [i] = i;
cout << data1 [i] << "";
}
cout << endl;
int index = -1;
// index = bisearch(data1、no2search、0、siz);
index = iterbisearch(data1、no2search、0、siz);
cout << "" << no2search << "is" << index << endl;
getchar();
0を返します。
}
コードコピーは次のとおりです。
/**
*アレイ内の文字の位置を見つけるための半分(注文リスト)
* @param配列取得アレイ
* @param xキャラクターが見つかります
* @returns配列内の文字の位置を返すと、結果は見つかりません-1
*/
function binarysearch(array、x){
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
var Midpoint;
var fund = false;
while((lowpoint <= higpoint)&&(!found)){
Midpoint = Math.ceil((lowpoint+higpoint)/2);
//console.log(lowpoint+"==="+midpoint+" ===="+higpoint);
if(x> array [midpoint-1]){
LowPoint = Midpoint+1;
}
else if(x <array [midpoint-1]){
higpoint = midpoint-1;
}
else if(x = array [midpoint-1]){
fund = true;
}
}
if(fund){
returnValue = midpoint;
}
ReturnValue;
}
/*var array2 = [1,2,3,4,5,6,7,8,9,100,109];*/
var array2 = ['a'、 'b'、 'c'、 'd'、 'e'、 'f'、 'g'];
console.log(binarysearch(array2、 'c'));