Wyszukiwanie binarne

W tym samouczku dowiesz się, jak działa sortowanie binarne. Znajdziesz również działające przykłady wyszukiwania binarnego w językach C, C ++, Java i Python.

Wyszukiwanie binarne to algorytm wyszukiwania służący do znajdowania pozycji elementu w posortowanej tablicy.

W tym podejściu element jest zawsze przeszukiwany w środku części tablicy.

Wyszukiwanie binarne można zaimplementować tylko na posortowanej liście elementów. Jeśli elementy nie są jeszcze posortowane, musimy je najpierw posortować.

Wyszukiwanie binarne działa

Algorytm wyszukiwania binarnego można zaimplementować na dwa sposoby, które omówiono poniżej.

  1. Metoda iteracyjna
  2. Metoda rekurencyjna

Metoda rekurencyjna jest zgodna z podejściem dziel i zwyciężaj.

Ogólne kroki dla obu metod omówiono poniżej.

  1. Tablica, w której ma być przeprowadzone wyszukiwanie to: Tablica początkowa
    Niech x = 4będzie elementem do przeszukania.
  2. Ustaw dwa wskaźniki odpowiednio nisko i wysoko na najniższej i najwyższej pozycji. Ustawianie wskaźników
  3. Znajdź środkowy element tablicy, tj. (arr(low + high)) / 2 = 6. Element środkowy
  4. Jeśli x == mid, a następnie zwróć mid.Else, porównaj szukany element z m.
  5. Jeśli x> midporównaj x ze środkowym elementem elementów po prawej stronie środka. Odbywa się to poprzez ustawienie niskiego na low = mid + 1.
  6. W przeciwnym razie porównaj x ze środkowym elementem elementów po lewej stronie środka. Odbywa się to poprzez ustawienie wysokiego na high = mid - 1. Znajdowanie elementu środkowego
  7. Powtarzaj kroki od 3 do 6, aż niski spotka się z wysokim. Element środkowy
  8. x = 4jest znalezione. Znaleziony

Algorytm wyszukiwania binarnego

Metoda iteracyjna

rób, dopóki wskaźniki niskie i wysokie nie spotkają się ze sobą. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x jest po prawej stronie low = mid + 1 else // x jest włączone lewa strona wysoko = środek - 1

Metoda rekurencyjna

 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 prawa strona return binarySearch (arr, x, mid + 1, high) else // x jest po prawej stronie return binarySearch (arr, x, low, mid - 1)

Python, Java, C / C ++ Przykłady (metoda iteracyjna)

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 ++ Przykłady (metoda rekurencyjna)

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

Złożoność wyszukiwania binarnego

Złożoność czasowa

  • Najlepsza złożoność przypadku :O(1)
  • Średnia złożoność sprawy :O(log n)
  • Złożoność najgorszego przypadku :O(log n)

Złożoność przestrzeni

Przestrzenna złożoność wyszukiwania binarnego wynosi O(n).

Aplikacje wyszukiwania binarnego

  • W bibliotekach Java, .Net, C ++ STL
  • Podczas debugowania wyszukiwanie binarne służy do wskazania miejsca wystąpienia błędu.

Interesujące artykuły...