Informatica I - Esercizi binsearch iterativo

Esercizio di laboratorio

Argomento: algoritmi di ricerca, ricerca su stringhe.

Realizzare un algoritmo di ricerca binaria (binarySearch) che funzioni in modo iterativo anziché ricorsivo.

Soluzione

Il metodo iterativeBinSearch effettua un accesso all'elemento intermedio dell'array ordinato, e se questo non contiene il valore cercato itera la ricerca sul semi-array superiore o inferiore, fino a quando:

• Non trova il valore cercato, oppure
• L'intervallo su cui effettuare la ricerca non diventa vuoto.

Prestare attenzione al fatto che il confronto di ordinamento tra stringhe avviene attraverso i metodi equals e compareTo.

Alg. di ricerca: binSearch iterativo

public static int iterativeBinSearch(String[] v, int vSize, String s){ int from = 0; int to = vSize - 1; while (from <= to){ int mid = (from + to) / 2; if (s.equals(v[mid])) return mid; else if (s.compareTo(v[mid]) < 0) to = mid - 1; else from = mid + 1;} return -1;}