{"id":4045,"date":"2024-09-19T13:05:15","date_gmt":"2024-09-19T11:05:15","guid":{"rendered":"https:\/\/www.capri-soft.de\/blog\/?p=4045"},"modified":"2024-09-19T13:05:15","modified_gmt":"2024-09-19T11:05:15","slug":"algorithmen-und-datenstrukutren-binaere-suche-vs-lineare-suche-in-java","status":"publish","type":"post","link":"https:\/\/www.capri-soft.de\/blog\/?p=4045","title":{"rendered":"Algorithmen und Datenstrukutren: Bin\u00e4re Suche vs. lineare Suche in JAVA"},"content":{"rendered":"\n
Der Algorithmus<\/h2>\n\n\n\n
Die bin\u00e4re Suche funktioniert nur auf einem bereits sortiertem Datenbestand, daher wird die Zeit f\u00fcr das Sortieren des Arrays \u201emyArray\u201c 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\u00e4sentativ.<\/p>\n\n\n
\npackage AlgoDat;\n \npublic class SearchAlgorithm {\n \/\/ Zu durchsuchendes Array\n private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};\n \n \/\/ H\u00e4lt die Klasse als instanziertes Objekt\n @SuppressWarnings("unused")\n private static SearchAlgorithm program;\n \n public int linearSearch(int[] array, int contentToSearchFor)\n {\n for (int i = 0; i < array.length; i++)\n {\n if (array[i] == contentToSearchFor)\n {\n return i;\n }\n }\n \n return -1;\n }\n \n public int binarySearch(int[] myArray, int contentToSearchFor)\n {\n \/\/ Start conditions\n int lowIndex = 0;\n int highIndex = myArray.length - 1;\n \n while (lowIndex <= highIndex)\n {\n int middlePosition = (lowIndex + highIndex) \/ 2;\n int middleContent = myArray[middlePosition];\n \n if (contentToSearchFor == middleContent) \n {\n return middlePosition;\n }\n \n \/\/ Halbieren der Suchelemente\n if (contentToSearchFor < middleContent)\n {\n highIndex = middlePosition - 1;\n }\n else\n {\n lowIndex = middlePosition + 1;\n }\n }\n \n \/\/ Au\u00dferhalb der While-Schleife wissen wir, dass wir\n \/\/ das Element nicht gefunden haben :-(\n return -1;\n }\n \n \/\/ Konstruktor\n public SearchAlgorithm()\n {\n int arrayContent = -1;\n long startTime = 0;\n long endTime = 0;\n int index = -1;\n long passedTime = 0;\n \n System.out.println("Lineare Suche");\n System.out.println("=============");\n \/\/ Not found\n arrayContent = 23;\n startTime = System.nanoTime();\n index = linearSearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");\n endTime = System.nanoTime();\n passedTime = endTime - startTime;\n System.out.println("Lineare Suche not found: " + passedTime + " ms.");\n \n \/\/ Best case\n arrayContent = 22;\n startTime = System.nanoTime();\n index = linearSearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");\n endTime = System.nanoTime();\n passedTime = endTime - startTime;\n System.out.println("Lineare Suche Best-Case: " + passedTime + " ms.");\n \n \/\/ Average case\n arrayContent = 3;\n startTime = System.nanoTime();\n index = linearSearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");\n endTime = System.nanoTime();\n passedTime = endTime - startTime;\n System.out.println("Lineare Suche Average-Case: " + passedTime + " ms.");\n \n \/\/ Worst case\n arrayContent = 1;\n startTime = System.nanoTime();\n index = linearSearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");\n endTime = System.nanoTime();\n passedTime = endTime - startTime;\n System.out.println("Lineare Suche Worst-Case: " + passedTime + " ms.");\n \n System.out.println("Bin\u00e4re Suche");\n System.out.println("============");\n \n \/*********************************************\/\n \/* die bin\u00e4re Suche ben\u00f6tigt ein sortiertes *\/\n \/* Array, damit sie funktioniert. *\/\n \/*********************************************\/\n startTime = System.nanoTime();\n this.mergeSort(myArray);\n endTime = System.nanoTime();\n long passedSortTime = endTime - startTime;\n \n \/\/ Not found\n arrayContent = 23;\n startTime = System.nanoTime();\n index = binarySearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");\n endTime = System.nanoTime();\n passedTime = passedSortTime + (endTime - startTime);\n System.out.println("Bin\u00e4re Suche not found: " + passedTime + " ms.");\n \n \/\/ Best case\n arrayContent = 22;\n startTime = System.nanoTime();\n index = binarySearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");\n endTime = System.nanoTime();\n passedTime = passedSortTime + (endTime - startTime);\n System.out.println("Bin\u00e4re Suche erstes Element: " + passedTime + " ms.");\n \n \/\/ Average case\n arrayContent = 3;\n startTime = System.nanoTime();\n index = binarySearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");\n endTime = System.nanoTime();\n passedTime = passedSortTime + (endTime - startTime);\n System.out.println("Bin\u00e4re Suche mittleres Element: " + passedTime + " ms.");\n \n \/\/ Worst case\n arrayContent = 1;\n startTime = System.nanoTime();\n index = binarySearch(myArray, arrayContent);\n System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");\n endTime = System.nanoTime();\n passedTime = passedSortTime + (endTime - startTime);\n System.out.println("Bin\u00e4re Suche letztes Element: " + passedTime + " ms.");\n }\n \n public static void main(String[] args) \n {\n \/\/ Instanziere aus den statischem Programm ein echtes Objekt\n \/\/ damit nicht alle Methoden und Variablen static sein m\u00fcssen.\n program = new SearchAlgorithm();\n }\n \n \/**************\/\n \/* MERGE SORT *\/\n \/**************\/\n \n public void mergeSort(int myArray[])\n {\n \/\/ Abbruchbedingung der Rekursion im Sinne von Teile-und-Herrsche-Algorithmen\n if (myArray.length == 1) return;\n \n \/\/ weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu\n int indexHaelfte = myArray.length \/ 2;\n \n int[] linkeHaelfte = new int[indexHaelfte];\n \n \/\/ Die abgerundete Ganzzahl kann von der L\u00e4nge abgezogen werden\n \/\/ um die Gr\u00f6\u00dfe des rechten Arrays zu erhalten.\n int[] rechteHaelfte = new int[myArray.length - indexHaelfte];\n \n \/\/ Bef\u00fclle die linke H\u00e4lfte \n for (int i = 0; i < indexHaelfte; i++)\n {\n linkeHaelfte[i] = myArray[i];\n }\n \n \/\/ Bef\u00fclle die rechte H\u00e4lfte \n for (int i = indexHaelfte; i < myArray.length; i++)\n {\n rechteHaelfte[i - indexHaelfte] = myArray[i];\n }\n \n \/\/ Hier ist der rekursive Aufruf, indem die beiden H\u00e4lften an\n \/\/ die mergeSort-Methode selbst \u00fcbergeben wird.\n this.mergeSort(linkeHaelfte);\n this.mergeSort(rechteHaelfte);\n \n \/\/ Hier werden die beiden Arrays wieder kombiniert (geMerged)\n this.merge(myArray, linkeHaelfte, rechteHaelfte);\n }\n \n private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)\n {\n int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;\n \n \/\/ Da die linke und reche H\u00e4lfte bereits sortiert sind, funktioniert die Zuweisung\n \/\/ in ein neues Array mit einer einzigen Schleife der Komplexit\u00e4t\/Ordnung O(n).\n while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)\n {\n if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])\n {\n mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];\n iteratorLinks++;\n }\n else\n {\n mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];\n iteratorRechts++;\n }\n \n iteratorMergeArray++;\n }\n \n \/\/ Wenn noch Elemente in der linken H\u00e4lfte waren, die nicht verglichen wurden,\n \/\/ werden diese dem Merged Array hinzugef\u00fcgt\n while (iteratorLinks < linkeHaelfte.length)\n {\n mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];\n iteratorLinks++;\n iteratorMergeArray++;\n }\n \n \/\/ Wenn noch Elemente in der rechten Array-H\u00e4lfte waren, die nicht verglichen wurden,\n \/\/ werden diese dem Merged Array hinzugef\u00fcgt\n while (iteratorRechts < rechteHaelfte.length)\n {\n mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];\n iteratorRechts++;\n iteratorMergeArray++;\n }\n }\n}\n<\/pre><\/div>\n\n\n
Ausgabe<\/h2>\n\n\n
\nLineare Suche\n=============\nDer Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Lineare Suche not found: 20969800 ms.\nDer Array-Element mit dem Inhalt '22' befindet sich am Index 0 von myArray[]. Lineare Suche Best-Case: 9613200 ms.\nDer Array-Element mit dem Inhalt '3' befindet sich am Index 5 von myArray[]. Lineare Suche Average-Case: 337400 ms.\nDer Array-Element mit dem Inhalt '1' befindet sich am Index 10 von myArray[]. Lineare Suche Worst-Case: 270200 ms.\n \nBin\u00e4re Suche\n============\nDer Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Bin\u00e4re Suche not found: 206800 ms.\nDer Array-Element mit dem Inhalt '22' befindet sich am Index 10 von myArray[]. Bin\u00e4re Suche erstes Element: 271400 ms.\nDer Array-Element mit dem Inhalt '3' befindet sich am Index 2 von myArray[]. Bin\u00e4re Suche mittleres Element: 306700 ms.\nDer Array-Element mit dem Inhalt '1' befindet sich am Index 0 von myArray[]. Bin\u00e4re Suche letztes Element: 302800 ms.\n<\/pre><\/div>\n\n\n
![\"\"](\"https:\/\/i0.wp.com\/www.capri-soft.de\/blog\/wp-content\/uploads\/2024\/09\/image-2.png?resize=92%2C21&ssl=1\")
<\/a><\/figure>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/www.capri-soft.de\/blog\/wp-content\/uploads\/2024\/09\/image-3.png?resize=210%2C21&ssl=1\")
<\/a><\/figure>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/www.capri-soft.de\/blog\/wp-content\/uploads\/2024\/09\/image-2.png?ssl=1\")
<\/a><\/figure>\n\n\n\n