Java >> Java Tutorial >  >> Java

Binäres Suchprogramm in Java

In diesem Beitrag werden wir sehen, wie man ein binäres Suchprogramm in Java schreibt. Die binäre Suche ist ein Teile-und-Herrsche-Algorithmus, der den Suchbereich in jeder Iteration um die Hälfte reduziert und sie somit effizienter macht als die lineare Suche .

Wie funktioniert die binäre Suche

Eine der Voraussetzungen für die binäre Suche ist, dass das Eingabearray sortiert ist .

Bei jeder Iteration wird das gesuchte Element mit dem mittleren Element des Arrays verglichen. Wenn das gesuchte Element kleiner als das mittlere Element des Arrays ist, bedeutet dies, dass das gesuchte Element zwischen dem Startelement und dem mittleren Element des Arrays liegen sollte, wenn das Array sortiert wird, sodass bei der nächsten Iteration die Suche mit dem Start des Unterarrays durchgeführt wird bis Mitte (0 bis (n/2-1)) und mit im Unterarray ((n/2+1) bis Ende), wenn das gesuchte Element größer als das mittlere Element ist.

Dieser Teilungs- und Suchprozess wird fortgesetzt, es sei denn, das Element wird gefunden oder die Länge des Unterarrays wird 0, was bedeutet, dass das gesuchte Element nicht im Array gefunden wird.

Das folgende Bild zeigt den Teilungsprozess in jeder Iteration

Java-Programm für die binäre Suche

Java-Programme für die binäre Suche können sowohl rekursiv als auch iterativ geschrieben werden. Wir werden diese beiden Lösungen hier sehen.

Binäre Suche in Java – Iteratives Programm

public class BinarySearch {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99};
    Arrays.sort(arr);
    System.out.println("sorted array- " + Arrays.toString(arr));
    System.out.println("Enter value to search: ");
    int searchElement = sc.nextInt();
    int index = binarySearch(arr, 0, arr.length-1, searchElement);
    if(index != -1){
      System.out.println("Searched item " + arr[index] + " found at index "+index);
    }else{
      System.out.println("Searched item " + searchElement + " not found in the array");
    }
  }
    
  private static int binarySearch(int[] arr, int start, int end, int searchElement){
    while(start <= end){
      int middle = (start+end)/2;
      System.out.println("start- " + start + " end " + end + " middle- " + middle);
      // element found
      if(searchElement == arr[middle]){
        return middle;
      }
      // left half
      if(searchElement < arr[middle]){
        end = middle - 1;
      }else{
          // right half
        start = middle + 1;
      }
    }
    return -1;
  }
}

Ausgabe

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73, 99]
Enter value to search: 
34
start- 0 end 9 middle- 4
start- 5 end 9 middle- 7
start- 5 end 6 middle- 5
Searched item 34 found at index 5

Binäre Suche in Java – Rekursives Programm

public class BinarySearch {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99};
    Arrays.sort(arr);
    System.out.println("sorted array- " + Arrays.toString(arr));
    System.out.println("Enter value to search: ");
    int searchElement = sc.nextInt();
    int index = binarySearch(arr, 0, arr.length-1, searchElement);
    if(index != -1){
      System.out.println("Searched item " + arr[index] + " found at index "+index);
    }else{
      System.out.println("Searched item " + searchElement + " not found in the array");
    }
  }
    
  private static int binarySearch(int[] arr, int start, int end, int searchElement){
    // exit condition
    if(start > end){
      return -1;
    }    
    int middle = (start+end)/2;
    System.out.println("start- " + start + " end " + end + " middle- " + middle);
    // element found
    if(searchElement == arr[middle]){
      return middle;
    }
    // left half
    if(searchElement < arr[middle]){
      return binarySearch(arr, start, middle-1, searchElement);
    }else{
      // right half
      return binarySearch(arr, middle+1, end, searchElement);        
    }
  }
}

Ausgabe

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73, 99]
Enter value to search: 
55
start- 0 end 9 middle- 4
start- 5 end 9 middle- 7
start- 5 end 6 middle- 5
start- 6 end 6 middle- 6
Searched item 55 found at index 6

Leistung der binären Suche

Die Zeitkomplexität der binären Suche ist O(logn).

Die Raumkomplexität der binären Suche ist O (1), da kein Hilfsraum benötigt wird. Obwohl die rekursive Lösung über Methodenstapel für jeden rekursiven Aufruf verfügt, wird die Raumkomplexität wie O(logn).

Das ist alles für dieses Thema Binäres Suchprogramm in Java . Wenn Sie Zweifel oder Vorschläge haben, hinterlassen Sie bitte einen Kommentar. Danke!


Java-Tag