Binaire zoekopdracht

In deze tutorial leert u hoe Binary Search-sortering werkt. Ook vindt u werkende voorbeelden van binair zoeken in C, C ++, Java en Python.

Binary Search is een zoekalgoritme voor het vinden van de positie van een element in een gesorteerde array.

Bij deze benadering wordt het element altijd in het midden van een gedeelte van een array doorzocht.

Binair zoeken kan alleen worden geïmplementeerd op een gesorteerde lijst met items. Als de elementen nog niet zijn gesorteerd, moeten we ze eerst sorteren.

Binair zoeken werkt

Binair zoekalgoritme kan op twee manieren worden geïmplementeerd, die hieronder worden besproken.

  1. Iteratieve methode
  2. Recursieve methode

De recursieve methode volgt de verdeel en heersbenadering.

De algemene stappen voor beide methoden worden hieronder besproken.

  1. De array waarin gezocht moet worden is: Initial array
    Laat x = 4het element zijn dat moet worden doorzocht.
  2. Zet twee pointers laag en hoog op respectievelijk de laagste en de hoogste positie. Aanwijzingen stellen
  3. Zoek het middelste element in het midden van de array, dwz. (arr(low + high)) / 2 = 6. Middenelement
  4. Als x == mid, retourneer dan mid.Else, vergelijk het te zoeken element met m.
  5. Als x> mid, vergelijk x met het middelste element van de elementen aan de rechterkant van mid. Dit wordt gedaan door laag in te stellen op low = mid + 1.
  6. Vergelijk anders x met het middelste element van de elementen aan de linkerkant van mid. Dit doe je door hoog in te stellen op high = mid - 1. Het middenelement vinden
  7. Herhaal stap 3 tot en met 6 totdat laag en hoog elkaar ontmoeten. Middenelement
  8. x = 4is gevonden. Gevonden

Binair zoekalgoritme

Iteratiemethode

doe totdat de wijzers laag en hoog elkaar ontmoeten. mid = (laag + hoog) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x staat aan de rechterkant low = mid + 1 else // x staat aan de linkerkant hoog = midden - 1

Recursieve methode

 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 staat op de rechterkant return binarySearch (arr, x, mid + 1, high) else // x staat aan de rechterkant return binarySearch (arr, x, low, mid - 1)

Python, Java, C / C ++ voorbeelden (iteratieve methode)

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

Python, Java, C / C ++ voorbeelden (recursieve methode)

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

Binaire zoekcomplexiteit

Tijdscomplexiteit

  • Complexiteit in het beste geval :O(1)
  • Gemiddelde casuscomplexiteit :O(log n)
  • Complexiteit in het ergste geval :O(log n)

Complexiteit van de ruimte

De ruimtecomplexiteit van de binaire zoekopdracht is O(n).

Binaire zoektoepassingen

  • In bibliotheken van Java, .Net, C ++ STL
  • Tijdens het debuggen wordt de binaire zoekopdracht gebruikt om de plaats aan te wijzen waar de fout optreedt.

Interessante artikelen...