Binaarotsing

Selles õpetuses saate teada, kuidas binaarotsingu sortimine toimib. Samuti leiate toimivaid näiteid binaarotsingust C, C ++, Java ja Python.

Binaarotsing on otsingu algoritm sorditud massiivi elemendi positsiooni leidmiseks.

Selles lähenemises otsitakse elementi alati massiivi osa keskelt.

Binaarotsingut saab rakendada ainult üksuste järjestatud loendis. Kui elemente pole veel sorteeritud, peame need kõigepealt sorteerima.

Binaarotsing töötab

Binaarotsingu algoritmi saab rakendada kahel viisil, mida käsitletakse allpool.

  1. Iteratiivne meetod
  2. Rekursiivne meetod

Rekursiivne meetod järgib jagamise ja vallutamise lähenemist.

Mõlema meetodi üldisi samme käsitletakse allpool.

  1. Massiiv, milles otsida tuleb, on: Algmassiiv
    Laskma x = 4olema otsitav element.
  2. Pange kaks osutit madalale ja kõrgele vastavalt madalaimas ja kõrgeimas asendis. Näidikute seadmine
  3. Leidke massiivi keskmine element st. (arr(low + high)) / 2 = 6. Keskelement
  4. Kui x == keskel, siis naaske keskele. Muul juhul võrdle otsitavat elementi m-ga
  5. Kui x> midvõrrelda x-i keskel paremal küljel olevate elementide keskmise elemendiga. Seda saab teha seadistades madalaks väärtuseks low = mid + 1.
  6. Muul juhul võrrelge x keskel vasakul küljel olevate elementide keskmise elemendiga. Seda tehakse seadistades kõrge väärtusele high = mid - 1. Keskelementi leidmine
  7. Korrake samme 3 kuni 6, kuni madal on kõrge. Keskelement
  8. x = 4on leitud. Leitud

Binaarotsingu algoritm

Kordusmeetod

tehke seni, kuni madalad ja kõrged näitajad kohtuvad. keskel = (madal + kõrge) / 2, kui (x == arr (keskel)) naaseb keskel muul juhul, kui (x> A (keskel)) // x on paremal küljel vasak külg kõrge = keskel - 1

Rekursiivne meetod

 binarySearch (arr, x, low, high) kui madal> high return Väär muul juhul keskel = (low + high) / 2 kui x == arr (keskel) return keskel muul juhul, kui x <data (keskel) // x on parempoolne binaarotsingu tagastamine (arr, x, keskel + 1, kõrge)

Pythoni, Java, C / C ++ näited (iteratiivne meetod)

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

Pythoni, Java, C / C ++ näited (rekursiivne meetod)

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

Binaarotsingu keerukus

Aja keerukus

  • Parima juhtumi keerukus :O(1)
  • Keskmine juhtumi keerukus :O(log n)
  • Halvima juhtumi keerukus :O(log n)

Ruumi keerukus

Binaarotsingu ruumi keerukus on O(n).

Binaarotsingu rakendused

  • Java, .Net, C ++ STL raamatukogudes
  • Silumise ajal kasutatakse binaarotsingut vea tekkimise koha määramiseks.

Huvitavad Artiklid...