Binaarihaku

Tässä opetusohjelmassa opit, kuinka binäärihaun lajittelu toimii. Löydät myös toimivia esimerkkejä binäärihausta C, C ++, Java ja Python.

Binaarihaku on hakualgoritmi elementin sijainnin löytämiseksi lajitellusta taulukosta.

Tässä lähestymistavassa elementtiä etsitään aina matriisin osan keskeltä.

Binaarihaku voidaan toteuttaa vain lajiteltuun luetteloon. Jos elementtejä ei ole jo lajiteltu, meidän on ensin lajiteltava ne.

Binaarihaku toimii

Binaarihakualgoritmi voidaan toteuttaa kahdella tavalla, joita käsitellään jäljempänä.

  1. Iteratiivinen menetelmä
  2. Rekursiivinen menetelmä

Rekursiivinen menetelmä noudattaa jakamisen ja valloittamisen lähestymistapaa.

Molempien menetelmien yleisiä vaiheita käsitellään jäljempänä.

  1. Taulukko, jossa haku suoritetaan, on: Alkutaulukko
    Let x = 4on etsittävä elementti.
  2. Aseta kaksi osoittinta matalalle ja ylemmälle alimmalle ja ylemmälle sijainnille. Osoittimien asettaminen
  3. Etsi matriisin keskiosa eli. (arr(low + high)) / 2 = 6. Keskielementti
  4. Jos x == puolivälissä, palaa sitten keskelle, muuten, vertaa etsittävää elementtiä m: ään.
  5. Jos x> midvertaa x: tä keskiosan oikealla puolella olevien elementtien keskiosaan. Tämä tehdään asettamalla matalaksi arvoksi low = mid + 1.
  6. Muuten vertaa x: tä keskialueen vasemmalla puolella olevien elementtien keskiosaan. Tämä tehdään asettamalla korkeaksi high = mid - 1. Keskielementin löytäminen
  7. Toista vaiheet 3-6, kunnes matala saavuttaa korkean. Keskielementti
  8. x = 4on löydetty. Löytyi

Binaarihakualgoritmi

Iteraatiomenetelmä

tehdä, kunnes matalat ja korkeat osoittimet kohtaavat toisensa. mid = (matala + korkea) / 2 jos (x == arr (keskellä)) palaa keskelle muuta, jos (x> A (keskellä)) // x on oikealla puolella matala = keskellä + 1 muuta // x on päällä vasen puoli korkea = keskellä - 1

Rekursiivinen menetelmä

 binarySearch (arr, x, matala, korkea) jos matala> korkea tuotto Väärä muu keskiarvo = (matala + korkea) / 2 jos x == arr (keskellä) palaa keskellä muuta, jos x <data (keskellä) // x on oikeanpuoleinen paluu binaarihaku (arr, x, keski + 1, korkea) else // x on oikealla puolella paluu binaarihaku (arr, x, matala, puolivälissä - 1)

Python-, Java-, C / C ++ -esimerkkejä (iteratiivinen menetelmä)

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 ++ -esimerkkejä (rekursiivinen menetelmä)

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

Binaarihaun monimutkaisuus

Ajan monimutkaisuus

  • Paras tapa monimutkaisuus :O(1)
  • Keskimääräinen tapauksen monimutkaisuus :O(log n)
  • Pahimman tapauksen monimutkaisuus :O(log n)

Avaruuden monimutkaisuus

Binaarihaun avaruuden monimutkaisuus on O(n).

Binaarihakusovellukset

  • Java-, .Net-, C ++ STL -kirjastoissa
  • Virheenkorjauksen aikana binaarihakua käytetään paikan määrittämiseen, missä virhe tapahtuu.

Mielenkiintoisia artikkeleita...