Halbfindungsmethode falten :
Vergleichen Sie in einer geordneten Tabelle den Datenwert, der mit dem Intermediate -Element -Wert des Suchbereichs gesucht werden soll, und es werden drei Situationen geben:
1) Wenn der zu findene Datenwert genau gleich dem Zwischenelementwert ist, geben Sie den Index des Zwischenelementwerts zurück.
2) Wenn der zu gesuchte Datenwert kleiner als der Wert des Zwischenelements ist, verwenden Sie die erste Hälfte des gesamten Suchbereichs als neuer Suchbereich und führen Sie 1 aus) bis ein gleicher Wert gefunden wird.
3) Wenn der zu gesuchte Datenwert größer ist als der Wert des Zwischenelements, verwenden Sie die zweite Hälfte des gesamten Suchbereichs als neuer Suchbereich und führen Sie 1 aus) bis der gleiche Wert gefunden wird.
4) Wenn der gleiche Wert am Ende nicht gefunden werden kann, wird eine Fehlermeldung zurückgegeben.
Nach dem Binärbaum ist der mittlere Wert die Wurzel des binären Baums, die erste Hälfte ist der linke Teilbaum und die zweite Hälfte ist der rechte Teilbaum. Die Anzahl der Suche nach der halbfindenden Suchmethode ist genau die Anzahl der Ebenen, in denen sich der Wert befindet. Unter gleicher Wahrscheinlichkeit ungefähr
log2 (n+1) -1
Die Codekopie lautet wie folgt:
// Daten sind das zu durchsuchende Array, X ist der Datenwert, BEG ist der Beginn des Suchbereichs und zuletzt das Ende des Suchbereichs
// nicht rezisive Methode
int Bisarch (int data [], const int x, int bett, int zuletzt)
{
int Mid; // mittlere Position
if (bett> last)
{
Return -1;
}
while (bett <= last)
{
Mid = (Beg + Last) / 2;
if (x == Daten [Mid])
{
Mitte zurückkehren;
}
sonst wenn (Daten [Mid] <x)
{
bett = Mid + 1;
}
sonst wenn (Daten [Mid]> x)
{
last = Mid - 1;
}
}
Return -1;
}
// rekursive Methode
int iterbisearch (int data [], const int x, int bett, int zuletzt)
{
int Mid = -1;
Mid = (Beg + Last) / 2;
if (x == Daten [Mid])
{
Mitte zurückkehren;
}
sonst wenn (x <data [Mid])
{
return iterbisearch (Data, x, bett, Mid - 1);
}
sonst wenn (x> Daten [Mid])
{
return iterbisearch (data, x, Mid + 1, letztes);
}
Return -1;
}
// Hauptfunktion
int _tmain (int argc, _tchar* argv [])
{
int data1 [60] = {0};
int no2Search = 45;
cout << "Das Array ist:" << endl;
int siz = sizeof (data1)/sizeof (int);
für (int i = 0; i <siz; i ++)
{
Data1 [i] = i;
cout << data1 [i] << "";
}
cout << endl;
int index = -1;
// index = Bisarch (Data1, No2Search, 0, Siz);
index = iterbisearch (Data1, No2Search, 0, Siz);
cout << "Index von" << no2Search << "ist" << index << endl;
getChar ();
Rückkehr 0;
}
Die Codekopie lautet wie folgt:
/**
* Hälfte, um die Position der Zeichen im Array zu finden (Ordered List)
* @param Array Das abgerufene Array
* @param x Zeichen zu finden
* @return die Position des Zeichens im Array, keine gefundene Rückkehr -1
*/
Funktion Binarysearch (Array, x) {
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
var Midpoint;
var found = false;
while ((lowpoint <= higpoint) && (! gefunden)) {
Midpoint = Math.ceil ((Lowpoint+Higpoint)/2);
//console.log(lowpoint+"====="+ Midpoint+"===="+IGpoint);
if (x> Array [Mittelpunkt-1]) {
Lowpoint = Mittelpunkt+1;
}
sonst if (x <array [Mittelpunkt]) {
Higpoint = Mittelpunkt-1;
}
sonst if (x = Array [Mittelpunkt]) {
gefunden = wahr;
}
}
if (gefunden) {
returnValue = Mittelpunkt;
}
return 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'));