[JAVA] - binary search

[tigerjack89]

Ciao a tutti ragazzi!!
Ritorno con un ennesimo quesito esistenziale.

Ho realizzato un metodo binary search, non definito statico per altre ragioni, ma che comunque funziona su un vettore double[]. Il mio problema ora è andare ad implementare un modo per far restituire non tanto il valore -1 se non viene trovato l'elemento, quanto il valore (-(insertion point) - 1), proprio come fa il metodo binarySearch() della classe Arrays di java. Il problema è che, provando con varie soluzioni, non sono riuscito a venirne a capo.

Eccolo qui (a è il mio private double[]):

public int binarySearch(double number)
	{
		int low = 0;
		int high = a.length - 1;
		int insertionPoint = 0;
		
		while (low <= high)
		{
			int middle = (low + high) / 2;
			if (a[middle] == number)
				return middle;
			else if (a[middle] < number)
			{
				low = middle + 1;
				insertionPoint = low;
			}
			else
			{
				high = middle - 1;
				insertionPoint = high;
			}
		}

		if (high <= 0 || low <= 0) insertionPoint ++;
		return -insertionPoint - 1;
	}

Qualcuno saprebbe darmi una mano in merito?? Grazie mille in anticipo

[unomichisiada]

package test;

import java.util.Arrays;


public class TestBS{ 
    private double[] a = new double[]{1.2,3.17,15.3,15.33,16.0};


    public void createSortedRandomArray()
    {
	int MIN = 0;
	int MAX = 5000;

	//alloca l'array con 1000 posizioni
	a = new double[1000];

	//genera mille numeri random e li inserisce nell'array
	for (int i = 0; i < a.length; i++) {
	    a[i] = Math.random() * MAX - MIN + MAX;
	}

	//ordina l'array (prerequisito per la ricerca binaria 
	//è l'ordinamento dell'array in input)
	Arrays.sort(a);
    }

    public void printA()
    {
	if(a.length > 0)
	    System.out.print(a[0]);
	for (int i = 1; i < a.length; i++) {
	    System.out.print("," + a[i]);
	}
	System.out.println();
    }
    public double[] getA() {
	return a;
    }
    public int binarySerch(double number)
    {
	int i = 0;
	int j = a.length - 1;

	while (i <= j) {
	    int index = (i + j) / 2;
	    if (a[index] < number)
		i = index + 1;
	    else if (a[index] > number)
		j = index - 1;
	    else
		return index;
	}
	return -(i + 1);
    }
    public static void main(String[]args){
	TestBS test = new TestBS();

	//genera un array casuale ordinato di 1000 elementi
	test.createSortedRandomArray();

	//stampa l'array generato
	test.printA();

	//testa l'uguaglianza dei due algoritmi per 100000 volte
	double[] array = test.getA();
	boolean success = true;
	for (int i = 0; i < 100000; i++) {
	    //genera un numero random da 0 a 7000 da ricercare
	    double toSearch = Math.random() * 7000 - 0 + 7000;
	    //cerca con il mio algoritmo
	    int mine = test.binarySerch(toSearch);
	    //cerca con l'algoritmo java
	    int java = Arrays.binarySearch(test.getA(), toSearch);
	    if(mine != java)
	    {
		System.out.println("attenzione: i due algoritmi differiscono se si cerca il numero " + toSearch);
		success = false;
		break;
	    }
	}
	if(success)
	    System.out.println("i due algoritmi coincidono perfettamente");

    }
}

Ciao sopra ti ho scritto un'implementazione che soddisfa la tua richiesta e un metodo main di test che ti mostra come questo algoritmo sia perfettamente equivalente all'implementazione che trovi in Arrays

[tigerjack89]

Originariamente inviato da unomichisiada
...
Ciao sopra ti ho scritto un'implementazione che soddisfa la tua richiesta e un metodo main di test che ti mostra come questo algoritmo sia perfettamente equivalente all'implementazione che trovi in Arrays

Cavoli!! Grazie mille per l'aiuto!!
Dovrò studiarmi per bene tutta la classe perchè per me è tutt'altro che immediata...e a quest'ora il cervello è già quasi del tutto fritto!!Mi riprometto di farlo domani. Anche perchè è molto intrigante quel metodo di test

Grazie mille ancora!