Dvejetainė paieška

Šioje pamokoje sužinosite, kaip veikia „Dvejetainės paieškos“ rūšiavimas. Taip pat rasite veikiančių dvejetainės paieškos pavyzdžių C, C ++, Java ir Python.

Dvejetainė paieška yra paieškos algoritmas, skirtas surasti elemento poziciją surūšiuotame masyve.

Taikant šį metodą, elementas visada ieškomas masyvo dalies viduryje.

Dvejetainę paiešką galima įgyvendinti tik surūšiuotame elementų sąraše. Jei elementai jau nėra rūšiuojami, pirmiausia turime juos rūšiuoti.

Dvejetainės paieškos darbas

Dvejetainės paieškos algoritmą galima įgyvendinti dviem būdais, kurie aptarti toliau.

  1. Kartotinis metodas
  2. Rekursinis metodas

Rekurzinis metodas taikomas skaldyti ir užkariauti metodui.

Toliau aptariami bendri abiejų metodų žingsniai.

  1. Masyvas, kuriame turi būti atlikta paieška, yra: Pradinis masyvas
    Let x = 4yra ieškomas elementas.
  2. Nustatykite du žemus ir aukštus rodiklius atitinkamai žemiausioje ir aukščiausioje padėtyje. Rodyklių nustatymas
  3. Raskite vidurinį elementą masyvo viduryje, t. (arr(low + high)) / 2 = 6. Vidurinis elementas
  4. Jei x == vidurys, tada grįžkite vidurį. Kitaip palyginkite ieškomą elementą su m.
  5. Jei x> mid, palyginkite x su viduriniu elementų viduriniu elementu dešinėje vidurio dalyje. Tai daroma nustatant žemą į low = mid + 1.
  6. Kitu atveju palyginkite x su viduriniu elementų elementu kairėje vidurio pusėje. Tai daroma nustatant aukštą high = mid - 1. Vidurinio elemento radimas
  7. Pakartokite 3–6 veiksmus, kol žemas pasieks aukštą. Vidurinis elementas
  8. x = 4yra rastas. Rasta

Dvejetainės paieškos algoritmas

Kartojimo metodas

darykite tol, kol žemos ir aukštos rodyklės susitiks. vidurys = (žemas + aukštas) / 2, jei (x == arr (vidurys)) grįžta į vidurį, jei (x> A (vidurys)) // x yra dešinėje pusėje žemas = vidurys + 1 kitas // x yra įjungtas kairė pusė aukšta = vidurys - 1

Rekursinis metodas

 „binarinė paieška“ („arr“, „x“, „low“, „high“), jei „low“> „high return“ „False else mid =“ („low + high“) / 2, jei „x == arr“ („middle“ “), jei„ x <data (mid) // // “yra dešinioji pusė grąžina „binarinę paiešką“ („arr“, x, vidurio + 1, aukšta), kita // x yra dešinėje pusėje grąžina „binarinę paiešką“ („arr“, „x“, maža, vidurio - 1)

„Python“, „Java“, C / C ++ pavyzdžiai (kartotinis metodas)

„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 ++“ pavyzdžiai (rekursinis metodas)

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

Dvejetainės paieškos sudėtingumas

Laiko kompleksiškumas

  • Geriausio atvejo sudėtingumas :O(1)
  • Vidutinis atvejo sudėtingumas :O(log n)
  • Blogiausio atvejo sudėtingumas :O(log n)

Erdvės sudėtingumas

Dvejetainės paieškos erdvės sudėtingumas yra O(n).

Dvejetainės paieškos programos

  • „Java“, .Net, C ++ STL bibliotekose
  • Derinant, dvejetainė paieška naudojama norint nustatyti klaidos vietą.

Įdomios straipsniai...