Binárne vyhľadávanie

V tomto výučbe sa dozviete, ako funguje triedenie binárneho vyhľadávania. Nájdete tiež pracovné príklady binárneho vyhľadávania v jazykoch C, C ++, Java a Python.

Binárne vyhľadávanie je vyhľadávací algoritmus na vyhľadanie polohy prvku v zoradenom poli.

V tomto prístupe sa prvok vyhľadáva vždy uprostred časti poľa.

Binárne vyhľadávanie je možné implementovať iba na triedenom zozname položiek. Ak prvky ešte nie sú zoradené, musíme ich najskôr zoradiť.

Binárne vyhľadávanie funguje

Algoritmus binárneho vyhľadávania je možné implementovať dvoma spôsobmi, ktoré sú popísané nižšie.

  1. Iteratívna metóda
  2. Rekurzívna metóda

Rekurzívna metóda sleduje prístup rozdelenia a panovania.

Všeobecné kroky pre obidve metódy sú opísané nižšie.

  1. Pole, v ktorom sa má vykonať vyhľadávanie, je: Počiatočné pole
    Nech x = 4je prvok, ktorý sa má prehľadať.
  2. Nastavte dva ukazovatele nízko a vysoko na najnižšiu a najvyššiu pozíciu. Nastavovanie ukazovateľov
  3. Nájdite stredný prvok v strede poľa, tj. (arr(low + high)) / 2 = 6. Stredný prvok
  4. Ak je x == stred, potom sa vráťte do stredu. Else, porovnajte hľadaný prvok s m.
  5. Ak x> mid, porovnajte x so stredným prvkom prvkov na pravej strane stredu. To sa dosiahne nastavením nízkej na low = mid + 1.
  6. Inak porovnajte x so stredným prvkom prvkov na ľavej strane stredu. To sa deje nastavením vysokej na high = mid - 1. Nájdenie stredného prvku
  7. Opakujte kroky 3 až 6, kým sa nízka nedosiahne vysoká. Stredný prvok
  8. x = 4je nájdený. Nájdené

Algoritmus binárneho vyhľadávania

Iteračná metóda

robte dovtedy, kým sa ukazovatele nízke a vysoké nestretnú. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x is on the right side low = mid + 1 else // x is on ľavá strana vysoká = stred - 1

Rekurzívna metóda

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return mid else if x <data (mid) // x is on the pravá strana vrátiť binarySearch (arr, x, stred + 1, vysoká) else // x je na pravej strane vrátiť binárne vyhľadávanie (arr, x, stredná + 1, vysoká)

Príklady jazyka Python, Java, C / C ++ (iteračná metóda)

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

Príklady Pythonu, Javy, C / C ++ (rekurzívna metóda)

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

Zložitosť binárneho vyhľadávania

Časové zložitosti

  • Najlepšia zložitosť prípadu :O(1)
  • Priemerná zložitosť prípadu :O(log n)
  • Najhoršia zložitosť prípadu :O(log n)

Zložitosť vesmíru

Priestorová zložitosť binárneho vyhľadávania je O(n).

Binárne vyhľadávacie aplikácie

  • V knižniciach Java, .Net, C ++ STL
  • Počas ladenia sa binárne vyhľadávanie používa na presné určenie miesta, kde sa chyba stala.

Zaujímavé články...