Căutare binară Algoritm este o algoritm de căutare folosit într-o matrice sortată de împărțind în mod repetat intervalul de căutare la jumătate . Ideea căutării binare este de a folosi informațiile că matricea este sortată și de a reduce complexitatea timpului la O(log N).

Ce este algoritmul de căutare binar?

Căutare binară este un algoritm de căutare utilizat pentru a găsi poziția unei valori țintă în a sortat matrice. Funcționează împărțind în mod repetat intervalul de căutare la jumătate până când este găsită valoarea țintă sau intervalul este gol. Intervalul de căutare este înjumătățit prin compararea elementului țintă cu valoarea de mijloc a spațiului de căutare.

cadru de colecție java

Pentru a aplica algoritmul de căutare binară:

• Structura datelor trebuie sortată.
• Accesul la orice element al structurii de date durează constant.

Algoritm de căutare binar:

În acest algoritm,

• Împărțiți spațiul de căutare în două jumătăți cu găsirea indicelui mijlociu mid .

Găsirea indicelui mijlociu la mijloc în algoritmul de căutare binar

• Comparați elementul din mijloc al spațiului de căutare cu cheia.
• Dacă cheia este găsită la elementul din mijloc, procesul este încheiat.
• Dacă cheia nu este găsită la elementul din mijloc, alegeți ce jumătate va fi folosită ca următorul spațiu de căutare.
  • Dacă cheia este mai mică decât elementul din mijloc, atunci partea stângă este folosită pentru următoarea căutare.
  • Dacă cheia este mai mare decât elementul din mijloc, atunci partea dreaptă este folosită pentru următoarea căutare.
• Acest proces este continuat până când cheia este găsită sau spațiul total de căutare este epuizat.

Cum funcționează algoritmul de căutare binar?

Pentru a înțelege funcționarea căutării binare, luați în considerare următoarea ilustrație:

Luați în considerare o matrice arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , si tinta = 23 .

Primul pas: Calculați mijlocul și comparați elementul mijlociu cu cheia. Dacă cheia este mai mică decât elementul mijlociu, deplasați-vă la stânga și dacă este mai mare decât mijlocul, mutați spațiul de căutare la dreapta.

• Cheia (adică 23) este mai mare decât elementul central actual (adică 16). Spațiul de căutare se deplasează spre dreapta.

Algoritm de căutare binar: comparați cheia cu 16

• Cheia este mai mică decât media actuală 56. Spațiul de căutare se deplasează la stânga.

Algoritm de căutare binar: comparați cheia cu 56

Al doilea pas: Dacă cheia se potrivește cu valoarea elementului mijlociu, elementul este găsit și se oprește căutarea.

Algoritm de căutare binar: cheia se potrivește cu mijlocul

Cum se implementează algoritmul de căutare binar?

The Algoritmul de căutare binar poate fi implementat în următoarele două moduri

• Algoritmul de căutare binar iterativ
• Algoritmul de căutare binar recursiv

Mai jos sunt date pseudocodurile pentru abordări.

Algoritm de căutare binar iterativ:

Aici folosim o buclă while pentru a continua procesul de comparare a cheii și de împărțire a spațiului de căutare în două jumătăți.

Implementarea algoritmului de căutare binară iterativă:

// 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 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 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);  } }>

# 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# 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);  } }>

// 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>= scăzut) { mijloc = scăzut + Math.floor((înalt - scăzut) / 2);    // Dacă elementul este prezent la mijloc // însuși if (arr[mid] == x) return mid;    // Dacă elementul este mai mic decât mijlocul, atunci // poate fi prezent numai în subbarraul stâng dacă (arr[mid]> x) high = mid - 1;    // Altfel, elementul poate fi prezent doar // în subbarra din dreapta else low = mid + 1;  } // Ajungem aici când elementul // nu este prezent în tabloul return -1; } arr =new Array(2, 3, 4, 10, 40);  x = 10;  n = lungimea arr.;  rezultat = binarySearch(arr, x);   (rezultat == -1) ? console.log('Elementul nu este prezent în matrice'): console.log ('Elementul este prezent la index ' + rezultat);   // Acest cod este contribuit de simranarora5sos și rshuclubb>

 // 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. ?>>>>  
  Ieșire  
Element is present at index 3>
  
    Complexitatea timpului:    O(log N)  
    Spațiu auxiliar:    O(1)
 
    Algoritm de căutare binar recursiv:    
 
Creați o funcție recursivă și comparați mijlocul spațiului de căutare cu cheia. Și pe baza rezultatului fie returnează indexul în care se găsește cheia, fie apelează funcția recursivă pentru următorul spațiu de căutare.
 
Implementarea algoritmului de căutare binar recursiv:
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>= low) { int mid = low + (high - low) / 2;  // Dacă elementul este prezent la mijloc // însuși if (arr[mid] == x) return mid;  // Dacă elementul este mai mic decât mijlocul, atunci // poate fi prezent numai în subbarraul stâng dacă (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Altfel, elementul poate fi prezent doar // în subbarra dreapta return binarySearch(arr, mid + 1, high, x);  } } // Cod driver int main() { int arr[] = { 2, 3, 4, 10, 40 };  interogare int = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int rezultat = binarySearch(arr, 0, n - 1, interogare);  (rezultat == -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>= low) { int mid = low + (high - low) / 2;  // Dacă elementul este prezent la mijloc // însuși if (arr[mid] == x) return mid;  // Dacă elementul este mai mic decât mijlocul, atunci // poate fi prezent numai în subbarraul stâng dacă (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Altfel, elementul poate fi prezent doar // în subbarra dreapta return binarySearch(arr, mid + 1, high, x);  } // Ajungem aici când elementul // nu este prezent în tabloul return -1; } // Cod driver int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int rezultat = binarySearch(arr, 0, n - 1, x);  (rezultat == -1) ? printf('Elementul nu este prezent în matrice'): printf('Elementul este prezent la indexul %d', rezultat);  întoarce 0; }>>>Java
 Piton 
# 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>= low: mid = low + (high - low) // 2 # Dacă elementul este prezent la mijloc, dacă arr[mid] == x: return mid # Dacă elementul este mai mic decât mijlocul, atunci poate fi prezent doar # în subbarra stânga elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Altfel, elementul poate fi prezent numai # în dreapta subbarray else: return binarySearch(arr, mid + 1, high, x ) # Elementul nu este prezent în matrice altfel: return -1 # Cod driver if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Rezultatul apelului funcției = binarySearch( arr, 0, len(arr)-1, x) dacă rezultat != -1: print('Elementul este prezent la index', rezultat) else: print('Elementul nu este prezent în matrice')> 
 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>= low) { int mid = low + (high - low) / 2;  // Dacă elementul este prezent la // mijlocul însuși if (arr[mid] == x) return mid;  // Dacă elementul este mai mic decât mijlocul, atunci // poate fi prezent numai în subbarraul stâng dacă (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Altfel, elementul poate fi prezent doar // în subbarra dreapta return binarySearch(arr, mid + 1, high, x);  } // Ajungem aici când elementul nu este prezent // în matrice return -1;  } // Cod driver public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Lungime;  int x = 10;  int rezultat = binarySearch(arr, 0, n - 1, x);  if (rezultat == -1) Console.WriteLine( 'Elementul nu este prezent în arrau');  else Console.WriteLine('Elementul este prezent la index ' + rezultat);  } } // Acest cod este contribuit de Sam007.>>>Javascript>>PHP>>
   
  Ieșire    Analiza complexității algoritmului de căutare binar:  
    Complexitatea timpului:     
Cel mai bun caz: O(1)
Cazul mediu: O(log N)
Cel mai rău caz: O(log N)
    Spațiu auxiliar:    O(1), Dacă se ia în considerare stiva de apeluri recursive, atunci spațiul auxiliar va fi O(logN).
     Aplicații ale algoritmului de căutare binar:     
Căutarea binară poate fi folosită ca element de bază pentru algoritmi mai complecși utilizați în învățarea automată, cum ar fi algoritmi pentru antrenarea rețelelor neuronale sau găsirea hiperparametrilor optimi pentru un model.
Poate fi folosit pentru căutarea în grafica computerizată, cum ar fi algoritmi pentru ray tracing sau cartografierea texturii.
Poate fi folosit pentru a căuta într-o bază de date.
    Avantajele căutării binare:    
Căutarea binară este mai rapidă decât căutarea liniară, în special pentru matrice mari.
Mai eficient decât alți algoritmi de căutare cu o complexitate de timp similară, cum ar fi căutarea prin interpolare sau căutarea exponențială.
Căutarea binară este potrivită pentru căutarea seturi de date mari care sunt stocate în memorie externă, cum ar fi pe un hard disk sau în cloud.
    Dezavantajele căutării binare:    
Matricea ar trebui să fie sortată.
Căutarea binară necesită ca structura de date căutată să fie stocată în locații de memorie adiacente.
Căutarea binară necesită ca elementele matricei să fie comparabile, ceea ce înseamnă că trebuie să poată fi ordonate.
Întrebări frecvente (Întrebări frecvente) privind Căutarea binară:
1. Ce este căutarea binară?
 
Căutarea binară este un algoritm eficient pentru găsirea unei valori țintă într-o matrice sortată. Funcționează împărțind în mod repetat intervalul de căutare la jumătate.
 
2. Cum funcționează Căutarea binară?
 
Căutarea binară compară valoarea țintă cu elementul din mijloc al matricei. Dacă sunt egale, căutarea are succes. Dacă ținta este mai mică decât elementul din mijloc, căutarea continuă în jumătatea inferioară a matricei. Dacă ținta este mai mare, căutarea continuă în jumătatea superioară. Acest proces se repetă până când ținta este găsită sau intervalul de căutare este gol.
 
3. Care este complexitatea temporală a Căutării binare?
 
Complexitatea temporală a căutării binare este O(log2n), unde n este numărul de elemente din matrice. Acest lucru se datorează faptului că dimensiunea intervalului de căutare este redusă la jumătate la fiecare pas.
 
4. Care sunt cerințele preliminare pentru Căutarea binară?
 
Căutarea binară necesită ca matricea să fie sortată în ordine crescătoare sau descrescătoare. Dacă matricea nu este sortată, nu putem folosi Căutarea binară pentru a căuta un element din matrice.
 
5. Ce se întâmplă dacă matricea nu este sortată pentru căutare binară?
 
Dacă matricea nu este sortată, căutarea binară poate returna rezultate incorecte. Se bazează pe natura sortată a matricei pentru a lua decizii cu privire la ce jumătate din matrice să caute.
 
6. Căutarea binară poate fi aplicată datelor nenumerice?
 
Da, căutarea binară poate fi aplicată datelor non-numerice atâta timp cât există o ordine definită pentru elemente. De exemplu, poate fi folosit pentru a căuta șiruri de caractere în ordine alfabetică.
javac nu este recunoscut
 
7. Care sunt unele dezavantaje comune ale Căutării binare?
 
Dezavantajul Căutării binare este că matricea de intrare trebuie sortată pentru a decide în ce jumătate se află elementul țintă. Prin urmare, pentru matricele nesortate, trebuie să sortăm matricea înainte de a aplica Căutarea binară.
 
8. Când ar trebui folosită Căutarea binară?
 
Căutarea binară ar trebui utilizată atunci când se caută o valoare țintă într-o matrice sortată, mai ales când dimensiunea matricei este mare. Este deosebit de eficient pentru seturile de date mari în comparație cu algoritmii de căutare liniară.
 
9. Căutarea binară poate fi implementată recursiv?
 
Da, căutarea binară poate fi implementată atât iterativ, cât și recursiv. Implementarea recursivă duce adesea la un cod mai concis, dar poate avea o suprasarcină puțin mai mare din cauza spațiului recursiv de stivă sau a apelurilor de funcții.
 
10. Căutarea binară este întotdeauna cea mai bună alegere pentru căutarea într-o matrice sortată?
 
În timp ce căutarea binară este foarte eficientă pentru căutarea în matrice sortate, pot exista cazuri specifice în care alți algoritmi de căutare sunt mai adecvați, cum ar fi atunci când se ocupă cu seturi de date mici sau când matricea este modificată frecvent.
 
    Articole similare:     
 
 Tutorial Căutare binară pe răspunsuri cu probleme 
 Căutare liniară vs căutare binară 
 Cum să identifici și să rezolvi problemele de căutare binară?