logo

TechCodeview

Binär sökalgoritm – Iterativ och rekursiv implementering

Binär sökning Algoritm är en sökalgoritm används i en sorterad array efter upprepade gånger dela sökintervallet på mitten . Tanken med binär sökning är att använda informationen som arrayen är sorterad och reducera tidskomplexiteten till O(log N).

Binär sökning är en sökalgoritm som används för att hitta positionen för ett målvärde inom en sorterad array. Det fungerar genom att upprepade gånger dela sökintervallet på mitten tills målvärdet hittas eller intervallet är tomt. Sökintervallet halveras genom att jämföra målelementet med sökutrymmets mittvärde.

tcp vs udp

Så här använder du binär sökalgoritm:



  • Datastrukturen måste sorteras.
  • Tillgång till alla element i datastrukturen tar konstant tid.

Binär sökalgoritm:

I denna algoritm,

  • Dela sökutrymmet i två halvor genom att hitta mittenindex mitt .

Hitta mitten av indexet mitt i binär sökalgoritm

  • Jämför mittelementet i sökutrymmet med nyckeln.
  • Om nyckeln hittas vid mittelementet avslutas processen.
  • Om nyckeln inte hittas vid mittelementet, välj vilken halva som ska användas som nästa sökutrymme.
    • Om nyckeln är mindre än mittelementet används den vänstra sidan för nästa sökning.
    • Om nyckeln är större än mittelementet används den högra sidan för nästa sökning.
  • Denna process fortsätter tills nyckeln hittas eller det totala sökutrymmet är slut.

Hur fungerar binär sökalgoritm?

För att förstå hur binär sökning fungerar, överväg följande illustration:

Överväg en array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , och den mål = 23 .

Första steget: Beräkna mitten och jämför mittelementet med nyckeln. Om nyckeln är mindre än mittelementet, flytta till vänster och om den är större än mitten flyttar du sökutrymmet till höger.

  • Nyckel (dvs 23) är större än nuvarande mittelement (dvs 16). Sökutrymmet flyttas till höger.

Binär sökalgoritm: Jämför nyckel med 16

  • Nyckeln är mindre än den nuvarande mitten av 56. Sökutrymmet flyttas till vänster.

Binär sökalgoritm: Jämför nyckel med 56

Andra steg: Om nyckeln matchar värdet på mittelementet, hittas elementet och stoppar sökningen.

Binär sökalgoritm : Nyckelmatchningar med mitten

Rekommenderad praxis Binär sökning Prova!

De Binär sökalgoritm kan implementeras på följande två sätt

  • Iterativ binär sökalgoritm
  • Rekursiv binär sökalgoritm

Nedan ges pseudokoderna för tillvägagångssätten.

Iterativ binär sökalgoritm:

Här använder vi en while-loop för att fortsätta processen med att jämföra nyckeln och dela upp sökutrymmet i två halvor.

Implementering av iterativ binär sökalgoritm:

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);  } }>
Pytonorm 
# 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>= låg) { mid = låg + Math.floor((hög - låg) / 2);    // Om elementet finns i mitten // sig själv if (arr[mid] == x) return mid;    // Om element är mindre än mid, då // kan det endast finnas i vänster undergrupp om (arr[mid]> x) high = mid - 1;    // Annars kan elementet bara vara närvarande // i höger subarray annars låg = mid + 1;  } // Vi når hit när element inte är // närvarande i array return -1; } arr =ny Array(2, 3, 4, 10, 40);  x = 10;  n = arr.längd;  result = binarySearch(arr, x);   (resultat == -1) ? console.log('Element finns inte i array') : console.log ('Element finns i index ' + resultat);   // Denna kod bidrar med simranarora5sos och 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>

Tidskomplexitet: O(log N)
Hjälputrymme: O(1)

Rekursiv binär sökalgoritm:

Skapa en rekursiv funktion och jämför mitten av sökutrymmet med nyckeln. Och baserat på resultatet returnerar du antingen indexet där nyckeln hittas eller anropar den rekursiva funktionen för nästa sökutrymme.

trådsynkronisering

Implementering av rekursiv binär sökalgoritm:

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>= låg) { int mid = låg + (hög - låg) / 2;  // Om elementet finns i mitten // sig själv if (arr[mid] == x) return mid;  // Om element är mindre än mid, då // kan det bara finnas i vänster underarray if (arr[mid]> x) returnerar binarySearch(arr, low, mid - 1, x);  // Annars kan elementet bara vara närvarande // i höger subarray returnerar binarySearch(arr, mid + 1, high, x);  } } // Drivrutinskod int main() { int arr[] = { 2, 3, 4, 10, 40 };  int query = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int resultat = binarySearch(arr, 0, n - 1, query);  (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>= låg) { int mid = låg + (hög - låg) / 2;  // Om elementet finns i mitten // sig själv if (arr[mid] == x) return mid;  // Om element är mindre än mid, då // kan det bara finnas i vänster underarray if (arr[mid]> x) returnerar binarySearch(arr, low, mid - 1, x);  // Annars kan elementet bara vara närvarande // i höger subarray returnerar binarySearch(arr, mid + 1, high, x);  } // Vi når hit när element inte är // närvarande i array return -1; } // Drivrutinskod int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int resultat = binarySearch(arr, 0, n - 1, x);  (resultat == -1) ? printf('Element finns inte i array') : printf('Element finns i index %d', resultat);  returnera 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>= låg) { int mid = låg + (hög - låg) / 2;  // Om elementet finns i // mitten själv if (arr[mid] == x) returnera mid;  // Om element är mindre än mid, då // kan det bara finnas i vänster underarray if (arr[mid]> x) returnerar binarySearch(arr, low, mid - 1, x);  // Annars kan elementet bara vara närvarande // i höger subarray returnerar binarySearch(arr, mid + 1, high, x);  } // Vi når hit när elementet inte finns // i array returnerar -1;  } // Driver code public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.längd;  int x = 10;  int resultat = ob.binarySearch(arr, 0, n - 1, x);  if (resultat == -1) System.out.println( 'Element finns inte i array');  else System.out.println( 'Element finns i index ' + resultat);  } } /* Denna kod är bidragit av Rajat Mishra */>
Pytonorm 
# 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>= låg: mitten = låg + (hög - låg) // 2 # Om elementet är närvarande i mitten om arr[mid] == x: returnera mitten # Om elementet är mindre än mitten, kan det # bara finnas närvarande i vänster undergrupp elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Annars kan elementet bara finnas # i höger underarray annars: return binarySearch(arr, mid + 1, high, x ) # Element finns inte i arrayen annars: 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 finns i index', resultat) else: print('Element finns inte 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>= låg) { int mid = låg + (hög - låg) / 2;  // Om elementet finns i // mitten själv if (arr[mid] == x) returnera mid;  // Om element är mindre än mid, då // kan det bara finnas i vänster underarray if (arr[mid]> x) returnerar binarySearch(arr, low, mid - 1, x);  // Annars kan elementet bara vara närvarande // i höger subarray returnerar binarySearch(arr, mid + 1, high, x);  } // Vi når hit när element inte finns // i array returnerar -1;  } // Driver code public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Längd;  int x = 10;  int resultat = binarySearch(arr, 0, n - 1, x);  if (resultat == -1) Console.WriteLine( 'Element finns inte i arrau');  else Console.WriteLine('Element finns i index ' + resultat);  } } // Den här koden är bidragit från 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>= låg) { let mid = low + Math.floor((hög - låg) / 2);  // Om elementet finns i mitten // sig själv if (arr[mid] == x) return mid;  // Om element är mindre än mid, då // kan det bara finnas i vänster underarray if (arr[mid]> x) returnerar binarySearch(arr, low, mid - 1, x);  // Annars kan elementet bara vara närvarande // i höger subarray returnerar binarySearch(arr, mid + 1, high, x);  } // Vi når hit när element inte är // närvarande i array return -1; } låt arr = [2, 3, 4, 10, 40]; låt x = 10; låt n = arr.längd låt resultat = binärsökning(arr, 0, n - 1, x); (resultat == -1) ? console.log( 'Element finns inte i array') : console.log('Element finns i index ' +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>= $låg) { $mid = ceil($låg + ($hög - $låg) / 2); // Om elementet finns // i själva mitten if ($arr[$mid] == $x) returnera floor($midt); // Om element är mindre än // mid, så kan det bara vara // närvarande i vänster undergrupp om ($arr[$mid]> $x) returnerar binarySearch($arr, $low, $mid - 1, $x ); // Annars kan elementet bara // vara närvarande i höger subarray return binarySearch($arr, $mid + 1, $high, $x); } // Vi når hit när element // inte finns i array return -1; } // Drivrutinskod $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element finns inte i array'; else echo 'Element är närvarande vid index ', $result; ?>>
Produktion 
Element is present at index 3>
  • Tidskomplexitet:
    • Bästa fall: O(1)
    • Genomsnittligt fall: O(log N)
    • Värsta fall: O(log N)
  • Hjälputrymme: O(1), Om den rekursiva anropsstacken beaktas kommer hjälputrymmet att vara O(logN).
  • Binär sökning kan användas som en byggsten för mer komplexa algoritmer som används i maskininlärning, såsom algoritmer för att träna neurala nätverk eller hitta de optimala hyperparametrarna för en modell.
  • Den kan användas för att söka i datorgrafik som algoritmer för ray tracing eller texturmapping.
  • Den kan användas för att söka i en databas.
  • Binär sökning är snabbare än linjär sökning, särskilt för stora arrayer.
  • Mer effektiv än andra sökalgoritmer med liknande tidskomplexitet, såsom interpolationssökning eller exponentiell sökning.
  • Binär sökning är väl lämpad för att söka i stora datamängder som är lagrade i externt minne, till exempel på en hårddisk eller i molnet.
  • Arrayen bör sorteras.
  • Binär sökning kräver att datastrukturen som genomsöks lagras på sammanhängande minnesplatser.
  • Binär sökning kräver att elementen i arrayen är jämförbara, vilket innebär att de måste kunna beställas.

Vanliga frågor (FAQs) om binär sökning:

1. Vad är binär sökning?

Binär sökning är en effektiv algoritm för att hitta ett målvärde inom en sorterad array. Det fungerar genom att upprepade gånger dela sökintervallet på mitten.

2. Hur fungerar binär sökning?

Binär sökning jämför målvärdet med mittelementet i arrayen. Om de är lika, är sökningen framgångsrik. Om målet är mindre än mittelementet fortsätter sökningen i den nedre halvan av arrayen. Om målet är större fortsätter sökningen i den övre halvan. Denna process upprepas tills målet hittas eller sökintervallet är tomt.

3. Vad är tidskomplexiteten för binär sökning?

Tidskomplexiteten för binär sökning är O(log2n), där n är antalet element i arrayen. Detta beror på att storleken på sökintervallet halveras i varje steg.

4. Vilka är förutsättningarna för binär sökning?

Binär sökning kräver att arrayen sorteras i stigande eller fallande ordning. Om arrayen inte är sorterad kan vi inte använda binär sökning för att söka efter ett element i arrayen.

5. Vad händer om arrayen inte sorteras för binär sökning?

Om arrayen inte är sorterad kan binär sökning returnera felaktiga resultat. Den förlitar sig på arrayens sorterade natur för att fatta beslut om vilken halva av arrayen som ska sökas.

6. Kan binär sökning tillämpas på icke-numeriska data?

Ja, binär sökning kan tillämpas på icke-numeriska data så länge det finns en definierad ordning för elementen. Den kan till exempel användas för att söka efter strängar i alfabetisk ordning.

7. Vilka är några vanliga nackdelar med binär sökning?

Nackdelen med binär sökning är att inmatningsmatrisen måste sorteras för att avgöra i vilken halva målelementet kan ligga. För osorterade arrayer måste vi därför sortera arrayen innan vi tillämpar binär sökning.

8. När ska binär sökning användas?

Binär sökning bör användas när du söker efter ett målvärde i en sorterad array, speciellt när storleken på arrayen är stor. Det är särskilt effektivt för stora datamängder jämfört med linjära sökalgoritmer.

9. Kan binär sökning implementeras rekursivt?

Ja, binär sökning kan implementeras både iterativt och rekursivt. Den rekursiva implementeringen leder ofta till mer koncis kod men kan ha något högre overhead på grund av rekursivt stackutrymme eller funktionsanrop.

10. Är binär sökning alltid det bästa valet för att söka i en sorterad array?

Även om binär sökning är mycket effektiv för att söka i sorterade arrayer, kan det finnas specifika fall där andra sökalgoritmer är mer lämpliga, till exempel när det handlar om små datamängder eller när arrayen ofta ändras.

Relaterade artiklar:

  • Handledning för binär sökning på svar med problem
  • Linjär sökning vs binär sökning
  • Hur identifierar och löser jag problem med binära sökningar?