Dvejetainė paieška yra viena iš paieškos metodų, taikomų rūšiuojant įvestį. Čia pagrindinis dėmesys skiriamas vidurinio elemento, kuris veikia kaip atskaitos rėmelis, paieška, nesvarbu, ar prie jo pereiti į kairę ar į dešinę, nes elementai jau surūšiuoti. Ši paieška padeda optimizuoti paieškos techniką atliekant kiekvieną iteraciją, vadinama dvejetaine paieška, o skaitytojai dėl to patiria stresą, nes ji netiesiogiai taikoma sprendžiant klausimus.
Dvejetainis paieškos algoritmas Java
Žemiau pateikiamas dvejetainei paieškai sukurtas algoritmas:
- Pradėti
- Paimkite įvesties masyvą ir Target
- Inicijuoti pradžia = 0 ir pabaiga = (masyvo dydis -1)
- Indijos vidurio kintamasis
- vidurys = (pradžia+pabaiga)/2
- if array[ mid ] == target then return mid
- jei masyvas[ mid ]
- jei masyvas[ mid ]> target tada pabaiga = mid-1
- jei pradžia<=pabaiga, pereikite prie 5 žingsnio
- grąžinti -1 kaip Elementas nerastas
- Išeiti
Dabar jūs turite galvoti, ką daryti, jei įvestis nėra surūšiuota, tada rezultatai neapibrėžti.
Pastaba: Jei yra dublikatų, nėra garantijos, kuris iš jų bus rastas.
Java dvejetainės paieškos metodai
Yra trys „Java“ diegimo būdai Dvejetainė paieška Java yra paminėti žemiau:
- Iteracinis metodas
- Rekursyvinis metodas
- Inbuild metodas
1. Iteratyvinis dvejetainės paieškos metodas Java
Toliau pateikiamas diegimas, paminėtas toliau:
Java
// Java implementation of iterative Binary Search> class> BinarySearch {> >// 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)> >{> >while> (l <= r) {> >int> mid = (l + r) />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> >// so we decrease our r pointer to mid - 1> >}>else> if> (arr[mid]>x) {> >r = mid ->1>;> >// Else the element can only be present> >// in right subarray> >// so we increase our l pointer to mid + 1> >}>else> {> >l = mid +>1>;> >}> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// Driver method to test above> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(>'Element not present'>);> >else> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
>
>Išvestis
mašinraščio foreach kilpa
Element found at index 3>
Patarimas: Geeks jums turi būti įdomu, ar yra kokia nors tokia funkcija apatinė riba() arba viršutinė_riba() Tikriausiai rasta C++ STL. taigi aiškus atsakymas, kad tik iki Java 9 funkcijos nebuvo, vėliau jos buvo pridėtos.
2. Rekursinis dvejetainės paieškos metodas
Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas:
Java
// Java implementation of> // recursive Binary Search> // Driver Class> class> BinarySearch {> >// 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)> >{> >if> (r>= l) {> >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>;> >}> >// main function> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(> >'Element is not present in array'>);> >else> >System.out.println(> >'Element is present at index '> + result);> >}> }> |
>
>Išvestis
Element is present at index 3>
Pirmiau minėto metodo sudėtingumas
Laiko sudėtingumas: O(log N)
Erdvės sudėtingumas: O(1), jei atsižvelgiama į rekursyvų skambučių krūvą, tada pagalbinė erdvė bus O(log N)
3. „Java“ dvejetainės paieškos kūrimo metodas
Arrays.binarysearch() veikia masyvams, kurie taip pat gali būti primityvaus tipo duomenų.
Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas:
Java
// Java Program to demonstrate working of binarySearch()> // Method of Arrays class In a sorted array> // Importing required classes> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring an integer array> >int> arr[] = {>10>,>20>,>15>,>22>,>35> };> >// Sorting the above array> >// using sort() method of Arrays class> >Arrays.sort(arr);> >int> key =>22>;> >int> res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>40>;> >res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Išvestis
22 found at index = 3 40 Not found>
Dvejetainė paieška Java kolekcijose
Dabar pažiūrėkime, kaip Collections.binarySearch() veikia LinkedList. Taigi iš esmės, kaip aptarta aukščiau, šis metodas veikia log(n) laiku laisvosios prieigos sąrašui, pvz., ArrayList. Jei nurodytas sąrašas neįdiegė RandomAccess sąsajos ir yra didelis, šis metodas atliks dvejetainę paiešką, pagrįstą iteratoriumi, kuri atlieka O(n) nuorodų perėjimą ir O(log n) elementų palyginimą.
Collections.binarysearch() veikia objektams Kolekcijos kaip ArrayList ir LinkedList .
Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas:
Java
// Java Program to Demonstrate Working of binarySearch()> // method of Collections class> // Importing required classes> import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty ArrayList of integer type> >List al =>new> ArrayList();> >// Populating the Arraylist> >al.add(>1>);> >al.add(>2>);> >al.add(>3>);> >al.add(>10>);> >al.add(>20>);> >// 10 is present at index 3> >int> key =>10>;> >int> res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>15>;> >res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Išvestis
10 found at index = 3 15 Not found>
Pirmiau minėto metodo sudėtingumas
Laiko sudėtingumas : O(log N)
Pagalbinė erdvė : O(1)