Java >> Java tutorial >  >> Java

Binær søgning i Java

Binær søgning i Java | Binær søgning er en effektiv algoritme til at finde et element fra en sorteret liste eller række af elementer. Nogle gange er det også kendt som halvintervalsøgning, logaritmisk søgning eller binær chop.

Tilstand for at bruge den binære søgning:- Arrayet skal sorteres i stigende rækkefølge.

Den binære søgealgoritme kan ikke anvendes på usorterede arrays. Denne algoritme kan bruges, når arrayet har termer, der forekommer i stigende størrelse (for eksempel:hvis termerne er tal, er de listet fra mindste til største; hvis de er ord, er de opført i leksikografisk eller alfabetisk rækkefølge) . Hvis arrayet eller listen ikke er sorteret, før du anvender den binære søgealgoritme, skal du først sortere arrayet eller listen.

Den binære søgealgoritme kan skrives på to måder. Disse er,
a) Rekursiv tilgang
b) Iterativ tilgang

Indholdsfortegnelse

  • Binær søgning i Java ved hjælp af rekursion
    • Binær søgealgoritme i Java ved hjælp af rekursion
    • Hvordan fungerer rekursiv tilgang?
    • Java-program til at implementere binær søgning ved hjælp af rekursion
  • Binær søgning i Java ved hjælp af iterativ tilgang
    • Algorithme
    • Java-program
  • Arrays.binarySearch()-metoden i Java
    • Eksempel ved hjælp af Arrays.binarySearch()
  • Binær søgetidskompleksitet

Binær søgning i Java ved hjælp af rekursion

I den rekursive tilgang anvendes rekursionsteknikken. Det er et eksempel på skille og hersk-teknikken, hvor større problemer er opdelt i mindre problemer. Ligesom alle dele og erob-algoritmer opdeler binær søgning først det store array i mindre sub-arrays og løs det derefter rekursivt. Vi vil se det i detaljer.

Binær søgealgoritme i Java ved hjælp af rekursion

a) Tag en matrix, startindeks, størrelse og søgenøgle.
b) Find mellemleddet.
c) Hvis mellemleddet ==søgnøgle, så returner indekset.
d) Hvis midterste term> søgetast, anvend derefter rekursivt kald på den første halvdel af arrayet.
e) Anvend ellers rekursivt kald på den anden halvdel af arrayet.
f) Gentag processen, indtil søgetasten ikke er matchet.
g) Hvis ikke matchet, så returner -1.

Den binære søgemetode i java ved hjælp af rekursion kan skrives som,

int binarySearch(arr, low, high, key) {
   if (high >= low) {
      int mid = low + (high - low) / 2; 
      if (arr[mid] == key) return mid; 
      if (arr[mid] > key) 
         return binarySearch(arr, low, mid - 1, key); 
      return binarySearch(arr, mid + 1, high, key); 
   }
   return -1; 
}

Tidskompleksiteten af ​​denne algoritme =O(log n)

Hvordan fungerer rekursiv tilgang til binær søgning?

I binær søgning ved hjælp af den rekursive tilgang opdeler vi arrayet fra midten i to subarrays af samme størrelse, eller hvor en af ​​disse mindre lister har en mindre term end den anden. Lad os forstå det gennem et eksempel.

Matrix ={10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

Eksempel

Antag søgetermen =40. Derefter trinene i binær søgning,

  1. Find det midterste led i arrayet. Hvis størrelsen af ​​array er ulige, så er mellemindeks =(størrelse - 1)/2 ellers mellemindeks =størrelse/2. I vores eksempel er mellemindeks =10/2 =5, og mellemled er array[3] =60
  2. Sammenlign mellemterm og søgeterm. Hvis mellemordet> søgeterm, kan det eksistere i den første del af arrayet ellers i den anden del af arrayet. Da 60> 40 derfor muligvis kun findes i den første del af arrayet.
  3. Opdel arrayet i to dele fra det midterste indeks. Subarr1 ={10, 20, 30, 40, 50} og subarr2 ={60, 70, 80, 90, 100}.
  4. Da arrayet er sorteret og 60> 40, findes søgetermer muligvis kun i den første underarray. Glemte det andet sub-array, ingen brug af det, kun det første sub-array er påkrævet til næste trin. Antag nu, at den oprindelige matrix ={10, 20, 30, 40, 50} og søgeterm =40.
  5. Gentag den samme proces med det første underarray. Find mellemleddet. Det midterste indeks =(5-1)/2 =2, mellemled er array[2] =30
  6. Sammenlign mellemterm med søgeterm, 30 <40, derfor findes den muligvis kun i den anden del.
  7. Opdel array i to underarrays fra det midterste indeks. De nye underarrays er:- subarr1 ={10, 20} og subarr2 ={30, 40, 50}. Kun subarr2 vil blive taget i betragtning til de næste trin, ingen brug af subarr1. Antag nu array ={30, 40, 50} og søgeterm =40. Gentag processen.
  8. Find mellem sigt. Det midterste indeks =(3-1)/2 =1 og mellemleddet er array[1] =40.
  9. Sammenlign mellemterm og søgeterm. I øjeblikket er begge ens, og matchen er fundet.

Java-program til implementering af binær søgning ved hjælp af rekursion

Lad os nu se implementeringen af ​​den binære søgealgoritme i programmeringssproget Java. Her finder metoden binarySearch() indekset for søgenøglen, hvis matchet findes, returnerer det indekset for søgenøglen ellers returnerer det -1.

public class Search {

   public static void main(String[] args) {
      int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
      int key = 40; // search key

      // binary search
      int index = binarySearch(arr, 0, arr.length, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);
   }

   // Method for binary search
   /* if match found then return index of search key
      else return -1 */
   public static int binarySearch(int[] arr, int low,
                           int high, int key) {
      if (high >= low) {
         // find middle index
         int mid = low + (high - low) / 2; 
     
         // find middle term and compare
         if (arr[mid] == key) return mid; // key found 
     
         // If key is smaller than middle term, then 
         // it can only be present in left subarray 
         if (arr[mid] > key) 
            return binarySearch(arr, low, mid - 1, key); 
     
         // Else the key can only be present 
         // in right subarray 
         return binarySearch(arr, mid + 1, high, key); 
      } 
     
      // key not found
      return -1; 
   }

}

Output:-

40 Fundet ved Index =3

Binær søgning i Java ved hjælp af iterativ tilgang

I denne tilgang bruger vi i stedet for at kalde metoden rekursivt iteration til at krydse arrayet og finde søgenøglen . Begge tilgange er ret ens, med to forskelle i implementering.

I den rekursive metode er der ingen løkke, og i stedet for at overføre de nye værdier til den næste iteration af løkken, sender den dem til den næste rekursion. I den iterative metode kan iterationerne styres gennem looping-betingelserne, mens i den rekursive metode bruges maksimum og minimum som grænsebetingelse.

Algorithme for binær søgning i Java ved hjælp af iterativ tilgang

For at søge efter heltal x i listen/arrayet a1 , en2 , … ,an , hvor array er i stigende rækkefølge (a1 2 <  ··· n) , 

  • begynd med at sammenligne x med mellemleddet am af listen/arrayet, hvor m =⌊(n + 1)/2⌋.
  • Hvis x> am , er søgningen efter x begrænset til anden halvdel af listen, som er enm+1 , am+2 , …, enn .
  • Hvis x ikke er større end am , er søgningen efter x begrænset til den første halvdel af listen, som er en1 , en2 , …, enm .
  • Søgningen er nu blevet begrænset til en liste med ikke mere end ⌊n/2⌋-elementer.
  • Sammenlign x med den midterste term på den begrænsede liste ved at bruge samme procedure.
  • Begræns derefter søgningen til den første eller anden halvdel af listen.
  • Gentag denne proces, indtil en liste med ét led er opnået.
  • Afgør derefter, om dette udtryk er x.

Algoritmen kan skrives som,

int binary search (a: array, lowIndex, highIndex,  x: search-key) {
   i = lowIndex; // i is left endpoint of search interval
   j = highIndex; // j is right endpoint of search interval
   while (i < j) {
      m = (i+j)/2; // floor of (i+j)/2
      if (x > a[m] ) then i = m+1;
      else j = m;
   }
   if (x=a[i]) then location = i;
   else location = -1;
   return location'
}

Program til binær søgning i Java ved hjælp af iterativ tilgang

Lad os nu se Java-programmet til binær søgning ved hjælp af den iterative tilgang,

import java.util.Scanner;

public class Search {

  public static void main(String[] args) {
    // Scanner class object to read input
    Scanner scan = new Scanner(System.in);

    // array
    int arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };

    // read search key
    System.out.print("Enter search key: ");
    int key = scan.nextInt();

    // binary search
    int index = binarySearch(arr, key);

    // display result
    if (index == -1)
      System.out.println(key + " not Found.");
    else
      System.out.println(key + " Found at Index = " + index);
    
    // close Scanner class object
    scan.close();

  }

  // binary search for complete array
  public static int binarySearch(int[] arr, int key) {
    // pass 0 as low value, array-size as high value
    return binarySearchRange(arr, 0, arr.length, key);
  }

  // Binary search method for a given range of array
  /* if match found then return index of 
   * search key else return -1
   */
  public static int binarySearchRange(int[] arr, 
                         int low, int high, int key) {
    int i = low; // left index
    int j = high; // right index
    int mid = 0;

    while (i < j) {
      // find middle index
      mid = (i + j) / 2;

      // compare search key and middle term
      if (key > arr[mid])
        i = mid + 1;
      else
        j = mid;
    }

    // when i==j
    if (key == arr[i])
      return i; // key found
    return -1; // key not found
  }
}

Output:-

Indtast søgenøgle:50
50 fundet ved indeks =4

Indtast søgenøgle:88
88 ikke fundet.

Arrays.binarySearch()-metoden i Java

Mens du arbejder med programmeringssproget Java, behøver du ikke at skrive den separate logik for den binære søgealgoritme. I klassen java.util.Arrays har vi en indbygget metode kaldet binarySearch(). Java Arrays-klassen blev introduceret i JDK 1.2-version, som indeholder forskellige metoder til at manipulere arrays såsom sortering, søgning, kopiering, konvertering af et array til streng og e.t.c.

Metoden Arrays.binarySearch() søger i det angivne array efter den angivne værdi ved hjælp af den binære søgealgoritme. Den bruger en iterativ tilgang ikke den rekursive metode.

Betingelse for at bruge Arrays.binarySearch()-metoden:- Arrayet skal sorteres i stigende rækkefølge. Hvis arrayet ikke er sorteret, vil resultaterne være udefinerede.

Hvis arrayet ikke er sorteret, kan vi bruge Arrays.sort() eller Arrays.parallelSort() til at sortere det givne array i stigende rækkefølge. Hvis arrayet indeholder flere elementer med den angivne værdi, er der ingen garanti for, hvilken der bliver fundet.

Der er flere overbelastede former for binarySearch()-metoden enten med rækkevidde eller uden rækkevidde.

  • public static int binarySearch(byte[] a, byte key)
  • public static int binarySearch(short[] a, short key)
  • public static int binarySearch(int[] a, int key)
  • public static int binarySearch(long[] a, long key)
  • public static int binarySearch(float[] a, float key)
  • public static int binarySearch(double[] a, double key)
  • public static int binarySearch(char[] a, char key)
  • public static int binarySearch(Object[] a, Object key)
  • public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
  • public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)
  • public static int binarySearch(short[] a, int fromIndex, int toIndex, short key)
  • public static int binarySearch(int[] a, int fromIndex, int toIndex, int key)
  • public static int binarySearch(long[] a, int fromIndex, int toIndex, long key)
  • public static int binarySearch(float[] a, int fromIndex, int toIndex, float key)
  • public static int binarySearch(double[] a, int fromIndex, int toIndex, double key)
  • public static int binarySearch(char[] a, int fromIndex, int toIndex, char key)
  • public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
  • public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)

Parametre i binarySearch()-metoden:-

  • a :- den matrix, der skal søges i
  • fra indeks :- indekset for det første element (inklusive), der skal søges i
  • til Indeks :- indekset for det sidste element (eksklusivt), der skal søges i
  • nøgle :- den værdi, der skal søges efter

Returværdi :- Det returnerer søgenøglens indeks. Hvis arrayet ikke indeholder en nøgle, returnerer det -1.

Eksempel på brug af Arrays.binarySearch()

Eksempel ved at bruge Arrays.binarySearch() i Java Arrays-klassen til at søge efter et element i et givet sorteret array,

import java.util.Arrays;

public class Search {
  public static void main(String[] args) {

    // array
    int arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };

    // search 85
    System.out.println("80 found at index = " 
                    + Arrays.binarySearch(arr, 80) );

    // search 75
    if (Arrays.binarySearch(arr, 75) != -1) {
      System.out.println("75 Found");
    } else {
      System.out.println("75 not Found");
    }
  }
}

Output:-

80 fundet ved indeks =7
75 fundet

Hvis arrayet ikke er sorteret i stigende rækkefølge, kan vi få det forkerte resultat. Hvis arrayet er sorteret, men i faldende rækkefølge, kan vi også få det forkerte resultat.

import java.util.Arrays;

public class Search {
  public static void main(String[] args) {

    // array
    int arr[] = { 100, 20, 30, 10, 50};

    // search 20
    System.out.println("20 found at index = " 
                       + Arrays.binarySearch(arr, 20));
  }
}

Output:-

20 fundet ved indeks =-1

Derfor, hvis array ikke er sorteret, før du kalder Arrays.binarySearch()-metoden, skal du sortere det givne array ved hjælp af Arrays.sort() eller Arrays.parallelSort(). Se:- Sådan sorteres et array i Java

import java.util.Arrays;

public class Search {
  public static void main(String[] args) {

    // array
    int arr[] = { 100, 20, 30, 10, 50};
    
    // display intial array
    System.out.println("Initial array = " 
                       + Arrays.toString(arr));
    
    // sort the array
    Arrays.sort(arr);
    
    // display array after sorting
    System.out.println("Array after Sorting= "  
                       + Arrays.toString(arr));

    // search 20
    System.out.println("20 found at index = "  
                       + Arrays.binarySearch(arr, 20));
  }
}

Output:-

Indledende matrix =[100, 20, 30, 10, 50]
Array efter sortering =[10, 20, 30, 50, 100]
20 fundet ved indeks =1

I dette program har vi brugt Arrays.toString()-metoden for at vise arrayet, som er givet til at konvertere arrayet til streng.

Lad os se endnu et Java-programeksempel ved hjælp af en binær søgealgoritme. Nu skriver vi ikke logikken for den binære søgealgoritme. I stedet kalder vi Arrays.binarySearch()-metoden, og hvis det er nødvendigt, vil vi først sortere det givne array.

Programbeskrivelse:- Skriv et Java-program for at søge efter en streng fra listen over strenge ved at bruge en binær søgealgoritme.

import java.util.Arrays;
import java.util.Scanner;

public class Search {
  public static void main(String[] args) {

    // unsorted array of String
    String arr[] = {"Java", "HTML", "C++", "Python", "CSS"};
    
    // display initial array
    System.out.println("Initial array = " 
                       + Arrays.toString(arr));
    
    // sort the array
    Arrays.sort(arr);
    
    // display array after sorting
    System.out.println("Initial array = " 
                       + Arrays.toString(arr));

    // Scanner class object to read input
    Scanner scan = new Scanner(System.in);
    
    // read character
    System.out.print("Enter a string to search: ");
    String str = scan.next();
    
    // search character
    int index = Arrays.binarySearch(arr, str);
    
    // display result
    if(index != -1)
      System.out.println(str + " found at index = " + index);
    else
      System.out.println(str+" not found.");
    
    // close Scanner
    scan.close();
  }
}

Output:-

Initial array =[Java, HTML, C++, Python, CSS]
Initial array =[C++, CSS, HTML, Java, Python]
Indtast en streng for at søge:Java
Java fundet på indeks =3

Initial array =[Java, HTML, C++, Python, CSS]
Initial array =[C++, CSS, HTML, Java, Python]
Indtast en streng for at søge:C#
C# ikke fundet .

Binær søgetidskompleksitet

Bedste tilfælde
tidskompleksitet 
O(1) Når søgetasten findes i midten
(mellemled) af arrayet.
Worst case
tidskompleksitet
O(log n) Når søgetasten ikke er tilgængelig
eller yderst på listen.

I den iterative metode ville rumkompleksiteten være O(1). Mens i den rekursive metode ville rumkompleksiteten være O(log n).

For de små arrays giver lineær søgealgoritme bedre ydeevne sammenlignet med det binære array, men for de store arrays, hvis arrayet er i sorteret rækkefølge, giver den binære søgning bedre ydelse sammenlignet med den lineære søgning.

Der er specialiserede datastrukturer designet til hurtig søgning , såsom hash-tabeller , der kan søges mere effektivt end binær søgning. Binær søgning kan dog bruges til at løse en bredere række af problemer, såsom at finde det næstmindste eller næststørste element i arrayet i forhold til målet, selvom det er fraværende fra arrayet.


Java tag