logo

TechCodeview

Binær søgealgoritme – Iterativ og rekursiv implementering

Binær søgning Algoritme er en søgealgoritme bruges i et sorteret array efter gentagne gange at dele søgeintervallet i to . Ideen med binær søgning er at bruge informationen om, at arrayet er sorteret og reducere tidskompleksiteten til O(log N).

Binær søgning er en søgealgoritme, der bruges til at finde positionen af ​​en målværdi inden for en sorteret array. Det fungerer ved gentagne gange at dele søgeintervallet i to, indtil målværdien er fundet, eller intervallet er tomt. Søgeintervallet halveres ved at sammenligne målelementet med søgerummets midterste værdi.

smid undtagelseshåndtering i java

Sådan anvender du binær søgealgoritme:



  • Datastrukturen skal sorteres.
  • Adgang til ethvert element i datastrukturen tager konstant tid.

Binær søgealgoritme:

I denne algoritme,

  • Del søgefeltet i to halvdele ved finde det midterste indeks midt .

Find det midterste indeks midt i binær søgealgoritme

  • Sammenlign det midterste element i søgefeltet med tasten.
  • Hvis nøglen findes ved det midterste element, afsluttes processen.
  • Hvis nøglen ikke findes ved det midterste element, skal du vælge hvilken halvdel der skal bruges som næste søgefelt.
    • Hvis nøglen er mindre end det midterste element, bruges venstre side til næste søgning.
    • Hvis nøglen er større end det midterste element, bruges højre side til næste søgning.
  • Denne proces fortsættes, indtil nøglen er fundet, eller den samlede søgeplads er opbrugt.

Hvordan fungerer binær søgealgoritme?

For at forstå, hvordan binær søgning fungerer, skal du overveje følgende illustration:

Overvej et array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , og mål = 23 .

Første skridt: Beregn midten og sammenlign mellemelementet med nøglen. Hvis nøglen er mindre end midten af ​​elementet, skal du flytte til venstre, og hvis den er større end midten, skal du flytte søgefeltet til højre.

  • Nøgle (dvs. 23) er større end det nuværende midterste element (dvs. 16). Søgerummet flyttes til højre.

Binær søgealgoritme: Sammenlign nøgle med 16

  • Nøglen er mindre end den nuværende midt 56. Søgerummet flyttes til venstre.

Binær søgealgoritme: Sammenlign nøgle med 56

Andet trin: Hvis nøglen matcher værdien af ​​det midterste element, bliver elementet fundet, og søgningen stoppes.

Binær søgealgoritme: Nøglematches med mid

Anbefalet praksis Binær søgning Prøv det!

Det Binær søgealgoritme kan implementeres på følgende to måder

  • Iterativ binær søgealgoritme
  • Rekursiv binær søgealgoritme

Nedenstående er pseudokoderne for tilgangene.

Iterativ binær søgealgoritme:

Her bruger vi en while-løkke til at fortsætte processen med at sammenligne nøglen og dele søgerummet i to halvdele.

Implementering af iterativ binær søgealgoritme:

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
Java 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
Python 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
Javascript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= lav) { mid = lav + Math.floor((høj - lav) / 2);    // Hvis elementet er til stede i midten // sig selv if (arr[mid] == x) returner mid;    // Hvis element er mindre end mid, så // kan det kun være til stede i venstre subarray hvis (arr[mid]> x) high = mid - 1;    // Ellers kan elementet kun være til stede // i højre subarray ellers lav = mid + 1;  } // Vi når her, når element ikke er // til stede i array return -1; } arr =ny matrix(2, 3, 4, 10, 40);  x = 10;  n = arr.længde;  resultat = binærsøgning(arr, x);   (resultat == -1) ? console.log('Element er ikke til stede i array') : console.log ('Element er til stede ved indeks ' + resultat);   // Denne kode er bidraget af simranarora5sos og rshuklabbb>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
Produktion 
Element is present at index 3>

Tidskompleksitet: O(log N)
Hjælpeplads: O(1)

Rekursiv binær søgealgoritme:

Opret en rekursiv funktion og sammenlign midten af ​​søgefeltet med tasten. Og baseret på resultatet enten returnere indekset, hvor nøglen er fundet, eller kalde den rekursive funktion til det næste søgerum.

Implementering af rekursiv binær søgealgoritme:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= lav) { int mid = lav + (høj - lav) / 2;  // Hvis elementet er til stede i midten // sig selv if (arr[mid] == x) returner mid;  // Hvis element er mindre end mid, så // kan det kun være til stede i venstre subarray if (arr[mid]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet kun være til stede // i højre subarray returner binarySearch(arr, mid + 1, high, x);  } } // Driverkode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int forespørgsel = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int resultat = binær søgning(arr, 0, n - 1, forespørgsel);  (resultat == -1) ? cout<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= lav) { int mid = lav + (høj - lav) / 2;  // Hvis elementet er til stede i midten // sig selv if (arr[mid] == x) returner mid;  // Hvis element er mindre end mid, så // kan det kun være til stede i venstre subarray if (arr[mid]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet kun være til stede // i højre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når her, når element ikke er // til stede i array return -1; } // Driverkode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = størrelse på(arr) / størrelse på(arr[0]);  int x = 10;  int resultat = binær søgning(arr, 0, n - 1, x);  (resultat == -1) ? printf('Element er ikke til stede i array') : printf('Element er til stede ved indeks %d', resultat);  retur 0; }>
Java 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= lav) { int mid = lav + (høj - lav) / 2;  // Hvis elementet er til stede ved // midten selv if (arr[mid] == x) returner mid;  // Hvis element er mindre end mid, så // kan det kun være til stede i venstre subarray if (arr[mid]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet kun være til stede // i højre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når her, når element ikke er til stede // i array returnerer -1;  } // Driverkode public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = {2, 3, 4, 10, 40};  int n = arr.længde;  int x = 10;  int resultat = ob.binarySearch(arr, 0, n - 1, x);  if (resultat == -1) System.out.println( 'Element er ikke til stede i array');  else System.out.println( 'Element er til stede ved indeks ' + resultat);  } } /* Denne kode er bidraget af Rajat Mishra */>
Python 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= lav: mid = lav + (høj - lav) // 2 # Hvis element er til stede i selve midten, hvis arr[mid] == x: return mid # Hvis element er mindre end mid, så kan det # kun være til stede i venstre subarray elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Ellers kan elementet kun være til stede # i højre subarray else: return binarySearch(arr, mid + 1, high, x ) # Element er ikke til stede i arrayet andet: returner -1 # Driverkode hvis __navn__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Resultat af funktionskald = binær søgning( arr, 0, len(arr)-1, x) if result != -1: print('Element er til stede ved indeks', resultat) andet: print('Element er ikke til stede i array')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= lav) { int mid = lav + (høj - lav) / 2;  // Hvis elementet er til stede ved // midten selv if (arr[mid] == x) returner mid;  // Hvis element er mindre end mid, så // kan det kun være til stede i venstre subarray if (arr[mid]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet kun være til stede // i højre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når her, når element ikke er til stede // i array returnerer -1;  } // Driverkode offentlig statisk void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Længde;  int x = 10;  int resultat = binær søgning(arr, 0, n - 1, x);  if (resultat == -1) Console.WriteLine( 'Element er ikke til stede i arrau');  else Console.WriteLine('Element er til stede ved indeks ' + resultat);  } } // Denne kode er bidraget af Sam007.>
Javascript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= lav) { let mid = lav + Math.floor((høj - lav) / 2);  // Hvis elementet er til stede i midten // sig selv if (arr[mid] == x) returner mid;  // Hvis element er mindre end mid, så // kan det kun være til stede i venstre subarray if (arr[mid]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet kun være til stede // i højre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når her, når element ikke er // til stede i array return -1; } lad arr = [2, 3, 4, 10, 40]; lad x = 10; lad n = arr.længde lad resultat = binærSøg(arr, 0, n - 1, x); (resultat == -1) ? console.log( 'Element er ikke til stede i array') : console.log('Element er til stede ved indeks ' +resultat);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $low) { $mid = ceil($low + ($high - $low) / 2); // Hvis elementet er til stede // i selve midten if ($arr[$mid] == $x) returner floor($midt); // Hvis element er mindre end // mid, så kan det kun være // til stede i venstre subarray, hvis ($arr[$mid]> $x) returnerer binarySearch($arr, $low, $mid - 1, $x ); // Ellers kan elementet kun // være til stede i højre subarray return binarySearch($arr, $mid + 1, $high, $x); } // Vi når her, når element // ikke er til stede i array return -1; } // Driverkode $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binærsøgning($arr, 0, $n - 1, $x); if(($result == -1)) ekko 'Element er ikke til stede i array'; else echo 'Element er til stede ved indeks ', $result; ?>>
Produktion 
Element is present at index 3>
  • Tidskompleksitet:
    • Bedste tilfælde: O(1)
    • Gennemsnitligt tilfælde: O(log N)
    • Værste tilfælde: O(log N)
  • Hjælpeplads: O(1), Hvis den rekursive opkaldsstak tages i betragtning, vil hjælperummet være O(logN).
  • Binær søgning kan bruges som byggeklods til mere komplekse algoritmer brugt i maskinlæring, såsom algoritmer til træning af neurale netværk eller til at finde de optimale hyperparametre til en model.
  • Det kan bruges til at søge i computergrafik, såsom algoritmer til strålesporing eller teksturkortlægning.
  • Det kan bruges til at søge i en database.
  • Binær søgning er hurtigere end lineær søgning, især for store arrays.
  • Mere effektiv end andre søgealgoritmer med en lignende tidskompleksitet, såsom interpolationssøgning eller eksponentiel søgning.
  • Binær søgning er velegnet til at søge i store datasæt, der er gemt i ekstern hukommelse, såsom på en harddisk eller i skyen.
  • Arrayet skal sorteres.
  • Binær søgning kræver, at den datastruktur, der søges i, lagres i sammenhængende hukommelsesplaceringer.
  • Binær søgning kræver, at elementerne i arrayet er sammenlignelige, hvilket betyder, at de skal kunne bestilles.

Ofte stillede spørgsmål (FAQs) om binær søgning:

1. Hvad er binær søgning?

Binær søgning er en effektiv algoritme til at finde en målværdi i et sorteret array. Det virker ved gentagne gange at dele søgeintervallet i to.

2. Hvordan fungerer binær søgning?

Binær søgning sammenligner målværdien med det midterste element i arrayet. Hvis de er ens, er søgningen vellykket. Hvis målet er mindre end det midterste element, fortsætter søgningen i den nederste halvdel af arrayet. Hvis målet er større, fortsætter søgningen i den øverste halvdel. Denne proces gentages, indtil målet er fundet, eller søgeintervallet er tomt.

nuværende dato i java

3. Hvad er tidskompleksiteten af ​​binær søgning?

Tidskompleksiteten af ​​binær søgning er O(log2n), hvor n er antallet af elementer i arrayet. Dette skyldes, at størrelsen af ​​søgeintervallet halveres i hvert trin.

4. Hvad er forudsætningerne for binær søgning?

Binær søgning kræver, at arrayet er sorteret i stigende eller faldende rækkefølge. Hvis arrayet ikke er sorteret, kan vi ikke bruge binær søgning til at søge efter et element i arrayet.

5. Hvad sker der, hvis arrayet ikke er sorteret til binær søgning?

Hvis arrayet ikke er sorteret, kan binær søgning returnere forkerte resultater. Den er afhængig af arrayets sorterede natur for at træffe beslutninger om, hvilken halvdel af arrayet der skal søges i.

6. Kan binær søgning anvendes på ikke-numeriske data?

Ja, binær søgning kan anvendes på ikke-numeriske data, så længe der er en defineret rækkefølge for elementerne. For eksempel kan den bruges til at søge efter strenge i alfabetisk rækkefølge.

7. Hvad er nogle almindelige ulemper ved binær søgning?

Ulempen ved binær søgning er, at input-arrayet skal sorteres for at afgøre, i hvilken halvdel målelementet kan ligge. For usorterede arrays skal vi derfor sortere arrayet, før vi anvender binær søgning.

8. Hvornår skal binær søgning bruges?

Binær søgning bør bruges, når du søger efter en målværdi i et sorteret array, især når størrelsen af ​​arrayet er stort. Det er særligt effektivt for store datasæt sammenlignet med lineære søgealgoritmer.

9. Kan binær søgning implementeres rekursivt?

Ja, binær søgning kan implementeres både iterativt og rekursivt. Den rekursive implementering fører ofte til mere kortfattet kode, men kan have lidt højere overhead på grund af rekursiv stakplads eller funktionskald.

10. Er binær søgning altid det bedste valg til at søge i et sorteret array?

Mens binær søgning er meget effektiv til at søge i sorterede arrays, kan der være specifikke tilfælde, hvor andre søgealgoritmer er mere passende, såsom når man har at gøre med små datasæt, eller når arrayet ofte ændres.

Relaterede artikler:

  • Binær søgning på svar Tutorial med problemer
  • Lineær søgning vs binær søgning
  • Hvordan identificeres og løses binære søgeproblemer?