Bináris keresés

Ebben az oktatóanyagban megtudhatja, hogyan működik a bináris keresés rendezése. A bináris keresés működő példáit is megtalálja C, C ++, Java és Python nyelven.

A bináris keresés egy keresési algoritmus egy elem helyzetének megtalálásához egy rendezett tömbben.

Ebben a megközelítésben az elemet mindig egy tömb egy részének közepén keresik.

A bináris keresés csak az elemek rendezett listáján valósítható meg. Ha az elemek még nincsenek rendezve, akkor először rendezni kell őket.

Bináris keresési munka

A bináris keresési algoritmus kétféle módon valósítható meg, amelyeket az alábbiakban tárgyalunk.

  1. Iteratív módszer
  2. Rekurzív módszer

A rekurzív módszer a divide and conquer megközelítést követi.

Mindkét módszer általános lépéseit az alábbiakban tárgyaljuk.

  1. A tömb, amelyben a keresést el kell végezni, a következő: Kezdő tömb
    Legyen x = 4a keresendő elem.
  2. Állítson két mutatót alacsonyan és magasan a legalacsonyabb, illetve a legmagasabb pozícióban. Mutatók beállítása
  3. Keresse meg a tömb középső elemét, azaz. (arr(low + high)) / 2 = 6. Középső elem
  4. Ha x == közepe, akkor térjen vissza középre. Else, hasonlítsa össze a keresendő elemet m-vel.
  5. Ha x> mid, hasonlítsuk össze az x-et a középső elemek jobb oldalán a középső elemgel. Ezt úgy tehetjük meg, hogy alacsony értéket állítunk low = mid + 1.
  6. Egyébként hasonlítsuk össze az x-et a középső elem bal oldalán lévő elemek középső elemével. Ez úgy történik, hogy magasra állítja high = mid - 1. Közép elem keresése
  7. Ismételje meg a 3-6. Lépéseket, amíg az alacsony nem éri el a magas értéket. Középső elem
  8. x = 4található. Megtalált

Bináris keresési algoritmus

Iterációs módszer

addig, amíg az alacsony és magas mutatók nem találkoznak egymással. közép = (alacsony + magas) / 2, ha (x == arr (közép)) visszatér más közepére, ha (x> A (közép)) // x a jobb oldalon alacsony = közép + 1 másik // x be van kapcsolva a bal oldal magas = közepe - 1

Rekurzív módszer

 binarySearch (arr, x, alacsony, magas), ha alacsony> magas hozam Hamis más közép = (alacsony + magas) / 2, ha x == arr (közép) más közepén tér vissza, ha x <adat (közép) // jobb oldali bináris keresés (arr, x, közép + 1, magas) else // x a jobb oldalon visszatér bináris keresés (arr, x, alacsony, közepes - 1)

Példák Python, Java, C / C ++ (iteratív módszer)

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 ++ példák (rekurzív módszer)

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

Bináris keresés összetettsége

Időkomplexumok

  • Legjobb bonyolultság :O(1)
  • Átlagos esetösszetétel :O(log n)
  • Legrosszabb eset bonyolultság :O(log n)

Tér komplexitás

A bináris keresés térbeli összetettsége az O(n).

Bináris keresési alkalmazások

  • Java, .Net, C ++ STL könyvtárakban
  • A hibakeresés során a bináris keresést használják a hiba helyének meghatározására.

érdekes cikkek...