de javinpaul

Cum se implementeaza un algoritm de cautare binara in Java

Salutare tuturor! Am publicat o mulțime de algoritmi și articole despre structura datelor pe blogul meu, dar acesta este primul aici. În acest articol, vom examina popularitatea algoritmi fundamentali pentru interviuri.

Da, ai ghicit bine: trebuie să implementezi un căutare binară în Java și trebuie să scrieți atât algoritmi de căutare binari iterativi cât și recursivi.

În informatică, o căutare binară, sau căutare pe jumătate de interval, este o divizați și cuceriți algoritmul care localizează poziția unui articol într-un matrice sortată. Căutarea binară funcționează comparând o valoare de intrare cu elementul de mijloc al matricei.

Comparația determină dacă elementul este egal cu intrarea, este mai mic decât intrarea sau este mai mare decât intrarea.

Când elementul comparat este egal cu intrarea, căutarea se oprește și de obicei returnează poziția elementului.

ad-banner

Dacă elementul nu este egal cu intrarea, atunci se face o comparație pentru a determina dacă intrarea este mai mică sau mai mare decât elementul.

În funcție de rezultat, algoritm apoi începe din nou, dar căutând numai în partea de sus sau într-un subset al elementelor matricei.

Dacă intrarea nu este localizată în matrice, algoritmul va genera de obicei o valoare unică care indică acest lucru ca -1 sau doar aruncă un RuntimeException în Java, cum ar fi NoValueFoundException.

Algoritmii de căutare binară înjumătățesc în mod obișnuit numărul de elemente care trebuie verificate cu fiecare iterație succesivă, localizând astfel articolul dat (sau determinând absența acestuia) în timp logaritmic.

Btw, dacă nu sunteți familiarizați cu algoritmii fundamentali de căutare și sortare, atunci vă puteți alătura și unui curs de genul Structuri de date și algoritmi: Deep Dive folosind Java pentru a învăța algoritmi fundamentali.

Cum se implementeaza un algoritm de cautare binara in Java

Dacă Java nu este alegerea limbii dvs., puteți găsi mai multe recomandări pentru JavaScript și Python în aceasta lista cursurilor de algoritmi.

Btw, dacă preferați cărțile, vă sugerez să citiți o carte cuprinzătoare de algoritmi de genul Introducere în algoritmi de Thomas H. Cormen.

1611749466 814 Cum se implementeaza un algoritm de cautare binara in Java

Iată câteva exemple de cod care arată logica căutare binară iterativă în Java:

1611749466 633 Cum se implementeaza un algoritm de cautare binara in Java

Implementarea căutării binare în Java

Iată un exemplu de program pentru implementarea căutării binare în Java. Algoritmul este implementat recursiv. De asemenea, un fapt interesant de știut despre implementarea căutării binare în Java este că Joshua Bloch, autorul faimosului Java eficient carte, a scris căutarea binară în „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.

Cam asta e tot cum se implementează căutarea binară folosind recursivitatea în Java. Împreună cu căutarea liniară, aceștia sunt doi dintre algoritmii esențiali de căutare pe care îi învățați la ora dvs. de informatică.

Structura de date a arborelui de căutare binară profită de acest algoritm și aranjează datele într-o structură ierarhică, astfel încât să puteți căuta orice nod în timpul O (logN).

Totuși, trebuie să vă amintiți că, pentru a utiliza căutarea binară, aveți nevoie de o listă sau o matrice sortată, deci trebuie să luați în considerare și costul sortării atunci când luați în considerare utilizarea algoritmului de căutare binară în lumea reală.

Învățare ulterioară
Structuri de date și algoritmi: Deep Dive folosind Java
Algoritmi și structuri de date – Partea 1 și 2
Structuri de date în Java 9 de Heinz Kabutz
10 cărți de algoritmi pentru interviuri
10 Cursuri de structură a datelor și algoritmi pentru interviuri
5 cursuri gratuite pentru a învăța structura datelor și algoritmi

Alte Tutoriale privind structura datelor și algoritmii s-ar putea să-ți placă

  • Cum se implementează algoritmul Quicksort în loc în Java? (tutorial)
  • Cum se implementează arborele de căutare binară în Java? (soluţie)
  • Cum se implementează algoritmul Quicksort fără recursivitate? (tutorial)
  • Cum se implementează algoritmul de sortare a inserției în Java? (tutorial)
  • Cum se implementează algoritmul de sortare Bubble în Java? (tutorial)
  • Care este diferența dintre algoritmul de sortare bazat pe comparație și fără comparație? (Răspuns)
  • Cum se implementează Sortarea Bucket în Java? (tutorial)
  • Cum se implementează un algoritm de căutare binară fără recursivitate în Java? (tutorial)
  • Cursuri de peste 50 de structuri de date și algoritmi pentru programatori (întrebări)

Vă mulțumim că ați citit acest articol. Dacă vă place acest articol, vă rugăm să împărtășiți prietenilor și colegilor dvs. Dacă aveți sugestii sau feedback, vă rugăm să renunțați la un comentariu.

PS – Dacă sunteți serios în ceea ce privește îmbunătățirea abilităților dvs. de algoritmi, cred că Structuri de date și algoritmi: Deep Dive folosind Java este cel mai bun pentru a începe.