/**
 * This is a solution for question 3) in Exercice 2, TD "algorithmique avancée"
 * 
 * This is not a complete class it will not compile!
 *
 */
List<Fiche> trouve (String nom, Paire [] index, Fiche [] base){
    int min=0, max=index.length, mid;
    boolean trouve=false;
    List<Fiche> res = new ArrayList<Fiche>();
    // Search for the right position
    while (min <= max&&!trouve){
	mid = min+max/2;
	if (nom.compareTo(index[mid].getNom())==0) trouve=true;
	else if  (nom.compareTo(index[mid].getNom())>0){
	    min=mid+1;
	}
	else{
	    max=mid-1;
	}
    }
    // Now we construct the list of matches
    int i=0;
    boolean plus = trouve;
    boolean minus = false;
    while (plus ||minus){
	// Last turn we updated the values of plus and minus
	if (plus)
	    res.add(base[index[mid+i].getNom()]);
	if (minus)
	    res.add(base[index[mid-i].getNom()]);
	// Do we need another turn?
	i++;
	if (mid+i<base.length)
	    plus = nom.compareTo(index[mid+i].getNom)==0;
	else plus=false;
	if (mid-i>=0)
	    minus = nom.compareTo(index[mid-i].getNom)==0;
	else minus=false;	    
    }
    return res;
}