Binarno iskanje

V tej vadnici boste izvedeli, kako deluje binarno razvrščanje. Prav tako boste našli delovne primere binarnega iskanja v jezikih C, C ++, Java in Python.

Binarno iskanje je iskalni algoritem za iskanje položaja elementa v razvrščeni matriki.

Pri tem pristopu element vedno iščemo sredi dela polja.

Binarno iskanje je mogoče izvajati samo na razvrščenem seznamu elementov. Če elementi še niso razvrščeni, jih moramo najprej razvrstiti.

Binarno iskanje deluje

Binarni algoritem iskanja je mogoče izvajati na dva načina, o katerih bomo razpravljali spodaj.

  1. Iterativna metoda
  2. Rekurzivna metoda

Rekurzivna metoda sledi pristopu deli in vladaj.

Splošni koraki za obe metodi so opisani v nadaljevanju.

  1. Matrika, v kateri naj bi se iskalo, je: Začetna matrika
    Naj x = 4bo element, ki ga je treba iskati.
  2. Nastavite dva kazalca nizko in visoko na najnižjem oziroma najvišjem položaju. Nastavitev kazalcev
  3. Poiščite srednji element sredi polja, tj. (arr(low + high)) / 2 = 6. Srednji element
  4. Če je x == mid, potem vrnite mid.Else, primerjajte iskani element z m.
  5. Če x> midprimerjajte x s srednjim elementom elementov na desni strani sredine. To naredimo tako, da nizko nastavimo na low = mid + 1.
  6. V nasprotnem primeru primerjajte x s srednjim elementom elementov na levi strani sredine. To se naredi tako, da visoko nastavite na high = mid - 1. Iskanje srednjega elementa
  7. Ponavljajte korake od 3 do 6, dokler nizka temperatura ne doseže visoke. Srednji element
  8. x = 4je najdeno. Najdeno

Binarni algoritem iskanja

Metoda ponavljanja

naredi, dokler se kazalca nizka in visoka ne srečata. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x je na desni strani low = mid + 1 else // x je vklopljen leva stran visoko = sredina - 1

Rekurzivna 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 desna stran vrne binarySearch (arr, x, mid + 1, high) else // x je na desni strani vrne binarySearch (arr, x, low, mid - 1)

Primeri Python, Java, C / C ++ (iterativna 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); )

Primeri Python, Java, C / C ++ (rekurzivna 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); )

Zapletenost binarnega iskanja

Časovne zapletenosti

  • Najboljša zapletenost primera :O(1)
  • Povprečna zahtevnost primera :O(log n)
  • Najslabša zapletenost primera :O(log n)

Zapletenost prostora

Prostorska zapletenost binarnega iskanja je O(n).

Aplikacije binarnega iskanja

  • V knjižnicah Java, .Net, C ++ STL
  • Med odpravljanjem napak se binarno iskanje uporablja za določitev mesta, kjer se napaka zgodi.

Zanimive Članki...