Taigi, kaip mes visi žinome dvejetainė paieška yra vienas iš paieškos algoritmų, kuris dažniausiai taikomas dirbant su duomenų struktūromis, kurių ekscentrinis tikslas nėra pereiti visą masyvą. Čia masyvas turi būti surūšiuotas, nes tikriname vidurinį elementą ir nepaisome pusės masyvo, kuri pagal skaičių sistemą nėra naudinga. Mes iš esmės ignoruojame pusę elementų tik po vieno palyginimo. Taip ir kartojame, kol elementas randamas, arba darome išvadą, kad elemento masyve nėra.
Algoritmai:
kažkas bf
- Palyginkite x su viduriniu elementu.
- Jei x atitinka vidurinį elementą, grąžiname vidurinį indeksą.
- Kitaip Jei x yra didesnis už vidurinį elementą, tai x gali būti tik dešinėje pusėje po vidurio elemento. Taigi mes kartojame dešinę pusę.
- Kitu atveju (x yra mažesnis) pasikartoja kairėje pusėje.
1 pavyzdys
Java
// Java Program to Illustrate> // Iterative Binary Search> // Main class> // BinarySearch> class> GFG {> >// Method 1> >// Returns index of x> >// if it is present in arr[],> >// else return -1> >int> binarySearch(>int> arr[],>int> x)> >{> >int> l =>0>, r = arr.length ->1>;> >// Checking element in whole array> >while> (l <= r) {> >int> m = l + (r - l) />2>;> >// Check if x is present at mid> >if> (arr[m] == x)> >return> m;> >// If x greater, ignore left half> >if> (arr[m] l = m + 1; // If x is smaller, // element is on left side // so ignore right half else r = m - 1; } // If we reach here, // element is not present return -1; } // Method 2 // Main driver method public static void main(String args[]) { GFG ob = new GFG(); // Input array int arr[] = { 2, 3, 4, 10, 40 }; // Length of array int n = arr.length; // Element to be checked if present or not int x = 10; // Calling the method 1 and // storing result int result = ob.binarySearch(arr, x); // Element present if (result == -1) // Print statement System.out.println('Element not present'); // Element not present else // Print statement System.out.println('Element found at index ' + result); } }> |
>
>Išvestis
Element found at index 3>
Laiko sudėtingumas : O(log n)
Pagalbinė erdvė : O(1)
2 pavyzdys
zip komanda Linux sistemoje
Java
// Java Program to Illustrate Recursive Binary Search> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Method 1> >// Recursive binary search> >// Returns index of x if it is present> >// in arr[l..r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >// Restrict the boundary of right index> >// and the left index to prevent> >// overflow of indices> >if> (r>= l && l<= arr.length ->1>) {> >int> mid = l + (r - l) />2>;> >// If the element is present> >// at the middle itself> >if> (arr[mid] == x)> >return> mid;> >// If element is smaller than mid, then it can> >// only be present in left subarray> >if> (arr[mid]>x)> >return> binarySearch(arr, l, mid ->1>, x);> >// Else the element can only be present> >// in right subarray> >return> binarySearch(arr, mid +>1>, r, x);> >}> >// We reach here when element is not present in> >// array> >return> ->1>;> >}> >// Method 2> >// Main driver method> >public> static> void> main(String args[])> >{> >// Creating object of above class> >GFG ob =>new> GFG();> >// Custom input array> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >// Length of array> >int> n = arr.length;> >// Custom element to be checked> >// whether present or not> >int> x =>10>;> >// Calling above method> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >// Element present> >if> (result == ->1>)> >// Print statement> >System.out.println(>'Element not present'>);> >// Element not present> >else> >// Print statement> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
>
>Išvestis
Element found at index 3>
Laiko sudėtingumas : O(log n)
Pagalbinė erdvė : O(1)