Căutare binară

În acest tutorial, veți afla cum funcționează sortarea Binary Search. De asemenea, veți găsi exemple de lucru ale Căutării binare în C, C ++, Java și Python.

Binary Search este un algoritm de căutare pentru găsirea poziției unui element într-o matrice sortată.

În această abordare, elementul este căutat întotdeauna în mijlocul unei porțiuni dintr-o matrice.

Căutarea binară poate fi implementată numai pe o listă sortată de articole. Dacă elementele nu sunt deja sortate, trebuie mai întâi să le sortăm.

Căutare binară funcționează

Algoritmul de căutare binară poate fi implementat în două moduri, care sunt discutate mai jos.

  1. Metoda iterativă
  2. Metoda recursivă

Metoda recursivă urmează abordarea divizării și cuceririi.

Pașii generali pentru ambele metode sunt discutați mai jos.

  1. Matricea în care se efectuează căutarea este: Matricea inițială
    Fie x = 4elementul care trebuie căutat.
  2. Setați două pointeri jos și înalt la pozițiile de jos și respectiv la cele mai înalte. Indicatori de setare
  3. Găsiți elementul de mijloc la mijlocul matricei, adică. (arr(low + high)) / 2 = 6. Element mijlociu
  4. Dacă x == mid, apoi întoarce mid. Altfel, compară elementul de căutat cu m.
  5. Dacă x> mid, comparați x cu elementul de mijloc al elementelor din partea dreaptă a mijlocului. Acest lucru se face prin setarea scăzută la low = mid + 1.
  6. Altfel, comparați x cu elementul din mijloc al elementelor din partea stângă a mijlocului. Acest lucru se realizează prin setarea ridicată la high = mid - 1. Găsirea elementului mijlociu
  7. Repetați pașii de la 3 la 6 până când valoarea minimă se ridică. Element mijlociu
  8. x = 4e gasit. Găsite

Algoritm de căutare binară

Metoda de iterație

faceți până când indicatoarele joasă și înaltă se întâlnesc. mid = (low + high) / 2 if (x == arr (mid)) returnează mid else if (x> A (mid)) // x este pe partea dreaptă low = mid + 1 else // x is on partea stângă ridicată = mijlocul - 1

Metoda recursivă

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return middle else if x <data (mid) // x este pe returnează binarySearch în partea dreaptă (arr, x, mid + 1, high) else // x este în partea dreaptă returnează binarySearch (arr, x, low, mid - 1)

Exemple Python, Java, C / C ++ (Metoda Iterativă)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Exemple Python, Java, C / C ++ (Metoda recursivă)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Complexitate de căutare binară

Complexități de timp

  • Complexitatea celui mai bun caz :O(1)
  • Complexitatea medie a cazurilor :O(log n)
  • Complexitatea celui mai prost caz :O(log n)

Complexitatea spațială

Complexitatea spațială a căutării binare este O(n).

Aplicații de căutare binare

  • În bibliotecile Java, .Net, C ++ STL
  • În timpul depanării, căutarea binară este utilizată pentru a identifica locul unde se întâmplă eroarea.

Articole interesante...