Der Algorithmus
Die binäre Suche funktioniert nur auf einem bereits sortiertem Datenbestand, daher wird die Zeit für das Sortieren des Arrays „myArray“ mit Merge-Sort auf die Such-Zeit addiert. Da die 11 Elemente im Beispiel-Array sehr wenige sind, sind die Zeiten in ms wenig repräsentativ.
package AlgoDat;
public class SearchAlgorithm {
// Zu durchsuchendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static SearchAlgorithm program;
public int linearSearch(int[] array, int contentToSearchFor)
{
for (int i = 0; i < array.length; i++)
{
if (array[i] == contentToSearchFor)
{
return i;
}
}
return -1;
}
public int binarySearch(int[] myArray, int contentToSearchFor)
{
// Start conditions
int lowIndex = 0;
int highIndex = myArray.length - 1;
while (lowIndex <= highIndex)
{
int middlePosition = (lowIndex + highIndex) / 2;
int middleContent = myArray[middlePosition];
if (contentToSearchFor == middleContent)
{
return middlePosition;
}
// Halbieren der Suchelemente
if (contentToSearchFor < middleContent)
{
highIndex = middlePosition - 1;
}
else
{
lowIndex = middlePosition + 1;
}
}
// Außerhalb der While-Schleife wissen wir, dass wir
// das Element nicht gefunden haben :-(
return -1;
}
// Konstruktor
public SearchAlgorithm()
{
int arrayContent = -1;
long startTime = 0;
long endTime = 0;
int index = -1;
long passedTime = 0;
System.out.println("Lineare Suche");
System.out.println("=============");
// Not found
arrayContent = 23;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche not found: " + passedTime + " ms.");
// Best case
arrayContent = 22;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche Best-Case: " + passedTime + " ms.");
// Average case
arrayContent = 3;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche Average-Case: " + passedTime + " ms.");
// Worst case
arrayContent = 1;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche Worst-Case: " + passedTime + " ms.");
System.out.println("Binäre Suche");
System.out.println("============");
/*********************************************/
/* die binäre Suche benötigt ein sortiertes */
/* Array, damit sie funktioniert. */
/*********************************************/
startTime = System.nanoTime();
this.mergeSort(myArray);
endTime = System.nanoTime();
long passedSortTime = endTime - startTime;
// Not found
arrayContent = 23;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche not found: " + passedTime + " ms.");
// Best case
arrayContent = 22;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche erstes Element: " + passedTime + " ms.");
// Average case
arrayContent = 3;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche mittleres Element: " + passedTime + " ms.");
// Worst case
arrayContent = 1;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche letztes Element: " + passedTime + " ms.");
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new SearchAlgorithm();
}
/**************/
/* MERGE SORT */
/**************/
public void mergeSort(int myArray[])
{
// Abbruchbedingung der Rekursion im Sinne von Teile-und-Herrsche-Algorithmen
if (myArray.length == 1) return;
// weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu
int indexHaelfte = myArray.length / 2;
int[] linkeHaelfte = new int[indexHaelfte];
// Die abgerundete Ganzzahl kann von der Länge abgezogen werden
// um die Größe des rechten Arrays zu erhalten.
int[] rechteHaelfte = new int[myArray.length - indexHaelfte];
// Befülle die linke Hälfte
for (int i = 0; i < indexHaelfte; i++)
{
linkeHaelfte[i] = myArray[i];
}
// Befülle die rechte Hälfte
for (int i = indexHaelfte; i < myArray.length; i++)
{
rechteHaelfte[i - indexHaelfte] = myArray[i];
}
// Hier ist der rekursive Aufruf, indem die beiden Hälften an
// die mergeSort-Methode selbst übergeben wird.
this.mergeSort(linkeHaelfte);
this.mergeSort(rechteHaelfte);
// Hier werden die beiden Arrays wieder kombiniert (geMerged)
this.merge(myArray, linkeHaelfte, rechteHaelfte);
}
private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)
{
int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;
// Da die linke und reche Hälfte bereits sortiert sind, funktioniert die Zuweisung
// in ein neues Array mit einer einzigen Schleife der Komplexität/Ordnung O(n).
while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)
{
if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
}
else
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
}
iteratorMergeArray++;
}
// Wenn noch Elemente in der linken Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorLinks < linkeHaelfte.length)
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
iteratorMergeArray++;
}
// Wenn noch Elemente in der rechten Array-Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorRechts < rechteHaelfte.length)
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
iteratorMergeArray++;
}
}
}
Ausgabe
Lineare Suche
=============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Lineare Suche not found: 20969800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 0 von myArray[]. Lineare Suche Best-Case: 9613200 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 5 von myArray[]. Lineare Suche Average-Case: 337400 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 10 von myArray[]. Lineare Suche Worst-Case: 270200 ms.
Binäre Suche
============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Binäre Suche not found: 206800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 10 von myArray[]. Binäre Suche erstes Element: 271400 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 2 von myArray[]. Binäre Suche mittleres Element: 306700 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 0 von myArray[]. Binäre Suche letztes Element: 302800 ms.
Komplexität: O-Notation (Ordnung)
Die Komplexität der binären Suche wird mit
beschrieben, wobei die Komplexität des vorangegangenen Merge-Sort-Algorithmus mitgerechnet werden muss, da die binäre Suche nur auf einem binären Datenbestand funktioniert. Somit ergibt sich
, wobei die additiven Bestandteile log(n) wegfallen. Somit ergibt sich im vorliegenden Falle die Komplexität O(n*log(n)) wegen der vorangegangen Sortierung. Ist diese nicht notwendig bleibt es bei der O-Notation O(log(n)).
