Einführung in die binäre Suche-PHP开发-php.cn

Einführung in die binäre Suche

高洛峰

Freigeben： 2016-12-19 16:29:39

Original

1760 Leute haben es durchsucht

Binäre Suche

Heute sprechen wir über „Binäre Suche“. Die Idee der binären Suche besteht darin, jedes Mal die Größe eines bestimmten Arrays in einem sequentiellen Array zu vergleichen. Der Nachteil der binären Suche besteht darin, dass das Array sequentiell sein muss (ich nehme als Beispiel die von klein nach groß sortierten Daten). Der Vorteil besteht darin, dass die Abfrageeffizienz extrem hoch ist und die Zeitkomplexität log2n beträgt. Je häufiger diese Suchmethode in Big Data eingesetzt wird, desto deutlicher wird der Effekt. Der Quellcode und der Unit-Test sind unten angehängt. Der Quellcode enthält zwei Algorithmen, einer ist eine Schleife und der andere ist rekursiv. Bitte beachten Sie:
Quellcode:

///

/// Verwenden Sie die binäre Methode, um den Ort eines Datenproblems zu finden. (Rekursive Methode)
/// Das Array muss von klein nach groß sortiert werden. Wenn es sich um unsortierte Daten handelt, können Sie verwenden = „StraightInsertionSort“/> Klasse zum Sortieren.
/// Wenn der zu findende Wert nicht im Array vorhanden ist, geben Sie -1 zurück.
/// & lt;//summary & gt; //// & lt; param name = "array" & lt;/param & gt; lt; "value" & gt; Der zu findende Wert
/// Gibt die Zahl zurück, wenn der zu findende Wert nicht im Array existiert, wird -1 Public static int Search(int [] array, int value)
                                                                                        ) { return array.Length - 1; }
return Search(array, 0, array.Length - 1, value);
}
private static int Search(int[] array, int beginIndex, int endIndex, int value)
int middle = (beginIndex + endIndex) / 2;
if (endIndex == beginIndex)
{ return array[beginIndex] == value ? beginIndex : -1 ; }
else if (endIndex == beginIndex + 1)
   y[endIndex] == value ) { return beginIndex; }                                                                                                                                       sonst wenn ( array[mitte ; (Schleifenmethode)
/// Das Array muss von klein nach groß sortiert werden. Wenn es sich um unsortierte Daten handelt, können Sie die Klasse verwenden cref= "StraightInsertionSort"/> Klasse zum Sortieren.
/// Wenn der zu findende Wert nicht im Array vorhanden ist, geben Sie -1 zurück.
/// & lt;//summary & gt; //// & lt; param name = "array" & lt;/param & gt; lt; "value" & gt; Der zu findende Wert
/// Gibt die Zahl zurück, die im Array nicht vorhanden ist ;
Public static int Search2(int [] array, int value)
int beginIndex = 0;
int endIndex = array.Length - 1;
while (true)
<= 1)
                                                                                                                                                                         🎜>    -1; }
                                                                                                                                                                     if (value < array[middle]) { endIndex = middle; }
if (value == array[middle]) { return middle; }
if (value > array[middle]) { beginIndex = middle; }
🎜> void SearchTest()
{

Random random = new Random();

int[] array2 = new int[100];
for (int i = 0; i < 100; i++)
{
array2[i] = random.Next(0, 1000);
}
int[] array3 = BitmapSort.Sort(array2);
for (int i = 0; i < array3.Length; i++)
{
Assert.AreEqual(BinarySearch.Search(array3, array3[i]), i);
Assert.AreEqual(BinarySearch.Search2(array3, array3[i]), i);
}
Assert.AreEqual(BinarySearch.Search(array3, 9999), -1);
Assert.AreEqual(BinarySearch.Search2(array3, 9999), -1);
}

更多二分法查找介绍相关文章请关注PHP中文网！