[Java] Consiglio su metodo sulla ricerca binaria ricorsiva

[cybergabry]

Ciao a tutti.
Vi vorrei chiedere un consiglio su come realizzare questo metodo che mi è stato richiesto in un esercizio. Premetto che non desidero avere risolto l'esercizio, ma solamente un consiglio su come procedere, altrimenti non imparo nulla . Sono autodidatta, non ho alcun professore a cui chiedere.
Esercizio: si scriva un metodo che implementi la ricerca binaria in maniera ricorsiva. Il metodo deve funzionare su array dello stesso tipo dell'elemento cercato.

Il seguente metodo funziona solo con array di tipo int:

public static int binario (int [] a, int n, int inizio, int fine)
{
	int centro = (inizio+fine)/2;
	if (inizio > fine)
		return -1;
	else if (a[centro] == n)
		return centro;
	else if (a[centro] < n)
		return binario(a, n, centro+1, fine);
	else
		return binario(a, n, inizio, centro-1);
}

Come faccio a farlo funzionare su array dello stesso tipo dell'elemento cercato? Grazie per l'aiuto.

[wingman87]

Dovresti usare i generici, non è un argomento semplicissimo però. Stai seguendo una guida?

[cybergabry]

Originariamente inviato da wingman87

Dovresti usare i generici, non è un argomento semplicissimo però. Stai seguendo una guida?

Sto seguendo un libro: "Programmazione in Java" della Apogeo.

Non conosco questi generici.

Nel libro c'è scritto che il metodo da me postato sopra può essere reso generico utilizzando il metodo compareTo() dell'inferfaccia Comparable per effettuare i confronti ma non capisco cosa intende dire.

[wingman87]

In effetti forse usare i generici è esagerato in questo caso. Puoi usare questa intestazione invece della precedente:

public static int binario (Comparable [] a, Comparable el, int inizio, int fine)

Ora sai che gli elementi di a possiedono il metodo compareTo() e quindi sei in grado di fare i confronti tra gli elementi.
Quando userai questo metodo gli passerai un array di oggetti che implementano Comparable (ad esempio String, oppure una classe creata da te).

[cybergabry]

Ho realizzato il software. Eclipse mi da dei warning in public static int binario (Comparable arr[], Comparable elem, int inizio, int fine) e precisamente nei primi due parametri.
Il warning è: "Comparable is a raw type. References to generic type Comparable<T> should be parameterized"
In effetti il programmino non funziona perchè mi dice sempre che l'elemento non è presente nell'array anche quando invece è presente.

import jbook.util.Input;
import java.util.Arrays;


public class RicercaBinaria {
	public static void main(String[] args) {	
		int quanti = Input.readInt("Quanti elementi vuoi inserire nell'array? ");
		String [] array = new String [quanti];
		for (int i=0; i < quanti; i++)
			array[i] = Input.readString("> ");
		Arrays.sort(array);
		String cercato = Input.readString("Inserisci l'elemento da cercare: ");
		int ris = binario(array, cercato, 0, quanti-1);
		if (ris == -1)
			System.out.println("Elemento non trovato");
		else
			System.out.println("L'elemento è presente nell'array");
	}
	public static int binario (Comparable arr[], Comparable elem, int inizio, int fine)
	{
		int centro = (inizio + fine)/2;
		if (inizio > fine)
			return -1;
		else if (elem == arr[centro])
			return centro;
		else if (elem.compareTo(arr[centro]) > 0)
			return binario (arr, elem, centro+1, fine);
		else
			return binario (arr, elem, inizio, centro-1);
	}

}

[banryu79]

Originariamente inviato da cybergabry

Il warning è: "Comparable is a raw type. References to generic type Comparable<T> should be parameterized"

Non preoccuparti di questo warning, per il momento, il tuo codice è sintatticamente corretto.
Se sei curioso, una spegazione del warning la trovi in questo post.

Originariamente inviato da cybergabry

In effetti il programmino non funziona perchè mi dice sempre che l'elemento non è presente nell'array anche quando invece è presente.

Ho letto al volo e ho notato questo:

public static int binario (Comparable arr[], Comparable elem, int inizio, int fine)
{
		int centro = (inizio + fine)/2;
		if (inizio > fine)
			return -1;
		else if (elem == arr[centro])
			return centro;
		else if (elem.compareTo(arr[centro]) > 0)
			return binario (arr, elem, centro+1, fine);
		else
			return binario (arr, elem, inizio, centro-1);
	}
}

se vuoi verificare l'uguaglianza tra due Comparable devi passarne uno come argomento al metodo compateTo dell'altro: se l'output restituito è zero allora sono considerati equivalenti (in termini di ordinamento).

if (elem.compareTo(arr[centro]) == 0)

[cybergabry]

[quote=banryu79;29641606][quote=cybergabry;29640287]
Il warning è: "Comparable is a raw type. References to generic type Comparable<T> should be parameterized"
[quote]
Non preoccuparti di questo warning, per il momento, il tuo codice è sintatticamente corretto.
Se sei curioso, una spegazione del warning la trovi in questo post.

[quote=cybergabry;29640287]
In effetti il programmino non funziona perchè mi dice sempre che l'elemento non è presente nell'array anche quando invece è presente.

Ho letto al volo e ho notato questo:

public static int binario (Comparable arr[], Comparable elem, int inizio, int fine)
{
		int centro = (inizio + fine)/2;
		if (inizio > fine)
			return -1;
		else if (elem == arr[centro])
			return centro;
		else if (elem.compareTo(arr[centro]) > 0)
			return binario (arr, elem, centro+1, fine);
		else
			return binario (arr, elem, inizio, centro-1);
	}
}

se vuoi verificare l'uguaglianza tra due Comparable devi passarne uno come argomento al metodo compateTo dell'altro: se l'output restituito è zero allora sono considerati equivalenti (in termini di ordinamento).

if (elem.compareTo(arr[centro]) == 0)

Grazie di tutto ho fatto come hai detto ed ho risolto. Ora vado a leggere il documento sui warning che mi hai linkato. Grazie ancora e arrivederci