Binární vyhledávání

V tomto kurzu se dozvíte, jak funguje třídění v binárním vyhledávání. Také najdete pracovní příklady binárního vyhledávání v jazycích C, C ++, Java a Python.

Binární vyhledávání je vyhledávací algoritmus pro vyhledání polohy prvku v seřazeném poli.

V tomto přístupu je prvek vždy prohledáván uprostřed části pole.

Binární vyhledávání lze implementovat pouze na seřazeném seznamu položek. Pokud prvky ještě nejsou seřazeny, musíme je nejprve seřadit.

Binární vyhledávání funguje

Algoritmus binárního vyhledávání lze implementovat dvěma způsoby, které jsou popsány níže.

  1. Iterativní metoda
  2. Rekurzivní metoda

Rekurzivní metoda sleduje přístup rozděl a panuj.

Obecné kroky pro obě metody jsou popsány níže.

  1. Pole, ve kterém má být vyhledávání provedeno, je: Počáteční pole
    Nechť x = 4je hledaný prvek.
  2. Nastavte dva ukazatele na nejnižší a nejvyšší na nejnižší a nejvyšší pozici. Nastavení ukazatelů
  3. Najděte střední prvek uprostřed pole, tj. (arr(low + high)) / 2 = 6. Střední prvek
  4. Pokud x == mid, pak se vraťte mid.Else, porovnejte hledaný prvek s m.
  5. Pokud x> mid, porovnejte x se středním prvkem prvků na pravé straně středu. To se provádí nastavením nízké na low = mid + 1.
  6. Jinak porovnejte x se středním prvkem prvků na levé straně středu. To se provádí nastavením vysoké na high = mid - 1. Nalezení prostředního prvku
  7. Opakujte kroky 3 až 6, dokud se nízká nesetká s vysokou. Střední prvek
  8. x = 4je nalezeno. Nalezeno

Algoritmus binárního vyhledávání

Iterační metoda

dělat, dokud se ukazatele nízké a vysoké nesetkají. 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 levá strana vysoká = střední - 1

Rekurzivní metoda

 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átit binarySearch (arr, x, mid + 1, high) else // x je na pravé straně vrátit binarySearch (arr, x, low, mid - 1)

Příklady Pythonu, Javy, C / C ++ (Iterativní metoda)

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

Příklady Pythonu, Javy, C / C ++ (rekurzivní metoda)

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

Složitost binárního vyhledávání

Časové složitosti

  • Nejlepší složitost případu :O(1)
  • Průměrná složitost případu :O(log n)
  • Složitost nejhoršího případu :O(log n)

Složitost vesmíru

Složitost prostoru binárního vyhledávání je O(n).

Binární vyhledávací aplikace

  • V knihovnách Java, .Net, C ++ STL
  • Při ladění se binární vyhledávání používá k určení místa, kde se chyba stala.

Zajímavé články...