Kako implementirati binarni algoritam pretraživanja u Javi bez rekurzije

Iterativna implementacija popularnog algoritma binarnog pretraživanja za pronalaženje elementa u razvrstanom nizu.

Pozdrav svima! Na svom sam blogu objavio puno članaka o algoritmima i strukturi podataka, ali ovaj je prvi ovdje. U ovom ćemo članku ispitati popularne temeljne algoritme za intervjue.

Da, dobro ste pogodili: morate implementirati binarno pretraživanje u Javi, a morate napisati i iterativni i rekurzivni algoritam binarnog pretraživanja.

U računalnim znanostima, binarno pretraživanje ili pretraživanje s pola intervala algoritam je podijeli i osvoji koji locira položaj stavke u razvrstanom nizu. Binarno pretraživanje funkcionira uspoređivanjem ulazne vrijednosti sa srednjim elementom niza.

Usporedbom se utvrđuje je li element jednak ulazu, je li manji od ulaza ili je veći od ulaza.

Kad je element koji se uspoređuje jednak ulazu, pretraživanje se zaustavlja i obično vraća položaj elementa.

Ako element nije jednak ulazu, tada se vrši usporedba kako bi se utvrdilo je li ulaz manji ili veći od elementa.

Ovisno o rezultatu, algoritam se zatim pokreće ispočetka, ali samo pretražujući gornji ili donji podskup elemenata niza.

Ako se ulaz ne nalazi u polju, algoritam će obično iznijeti jedinstvenu vrijednost koja označava ovo poput -1 ili jednostavno baciti RuntimeException u Javi poput NoValueFoundException.

Binarni algoritmi pretraživanja obično prepolove broj stavki koje treba provjeriti sa svakom uzastopnom iteracijom, locirajući tako zadanu stavku (ili utvrđujući njezinu odsutnost) u logaritamskom vremenu.

Btw, ako niste upoznati s osnovnim algoritmima pretraživanja i sortiranja, tada se također možete pridružiti tečaju kao što su Strukture podataka i Algoritmi: Dubinsko ronjenje Korištenjem Jave za učenje osnovnih algoritama.

Ako Java nije vaš jezik, na ovom popisu tečajeva algoritama možete pronaći više preporuka za JavaScript i Python.

Btw, ako više volite knjige, predlažem da pročitate opsežnu knjigu algoritama poput Uvod u algoritme Thomasa H. Cormena.

Evo nekoliko primjera koda koji pokazuje logiku iterativnog binarnog pretraživanja u Javi :

Implementacija binarnog pretraživanja u Javi

Evo primjera programa za implementaciju binarnog pretraživanja na Javi. Algoritam se implementira rekurzivno. Također, zanimljiva činjenica koju treba znati o implementaciji binarnog pretraživanja na Javi je da je Joshua Bloch, autor poznate knjige Effective Java, napisao binarno pretraživanje u "java.util.Arrays".

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

To je sve o tome kako implementirati binarno pretraživanje pomoću rekurzije u Javi . Zajedno s linearnim pretraživanjem, ovo su dva osnovna algoritma pretraživanja koja učite na satu informatike.

Struktura podataka binarnog stabla pretraživanja koristi prednost ovog algoritma i raspoređuje podatke u hijerarhijsku strukturu tako da možete pretraživati ​​bilo koji čvor u O (logN) vremenu.

Iako morate imati na umu da vam je za korištenje binarnog pretraživanja potreban razvrstani popis ili niz, tako da također trebate uzeti u obzir cijenu razvrstavanja kada razmišljate o upotrebi binarnog algoritma pretraživanja u stvarnom svijetu.

Daljnje učenje

Strukture podataka i algoritmi: dubinsko ronjenje pomoću Jave

Algoritmi i strukture podataka - 1. i 2. dio

Strukture podataka u Javi 9, Heinz Kabutz

10 knjiga o algoritmima za intervjue

10 Tečajevi strukture podataka i algoritma za intervjue

5 besplatnih tečajeva za učenje strukture podataka i algoritama

Ostali vodiči o strukturi podataka i algoritmima koji bi vam se mogli svidjeti

  • Kako implementirati Quicksort algoritam na mjestu u Javi? (tutorial)
  • Kako implementirati binarno stablo pretraživanja na Javi? (riješenje)
  • Kako implementirati Quicksort algoritam bez rekurzije? (tutorial)
  • Kako implementirati algoritam sortiranja umetanja u Javi? (tutorial)
  • How to implement Bubble sort algorithm in Java? (tutorial)
  • What is the difference between Comparison and Non-Comparison based sorting algorithm? (answer)
  • How to implement Bucket Sort in Java? (tutorial)
  • How to implement a Binary Search Algorithm without recursion in Java? (tutorial)
  • 50+ Data Structure and Algorithms Courses for Programmers (questions)

Thanks for reading this article. If you like this article then please share with your friends and colleagues. If you have any suggestion or feedback then please drop a comment.

P.S. — If you are serious about improving your Algorithms skills, I think the Data Structures and Algorithms: Deep Dive Using Java is the best one to start with.