// recherche-simple.c

// << Algorithmique du texte >>
// Maxime Crochemore, Christophe Hancart et Thierry Lecroq
// Vuibert, 2001.

#include <stdio.h>
#include "chl.h"
#include "llpc.h"


void rechercheSimple(Mot L[], int n, Mot x, Longueur m, int *resd, int *resf) {
   int d, f, i, ell;

   d = -1;
   f = n;
   while (d + 1 < f) {
      // Invariant : L[d] < x < L[f]
      i = (d + f)/2;
      ell = llpc(x, L[i]);
      if (ell == m && ell == strlen(L[i])) {
         *resd = *resf = i;
         return;
      }
      else if (ell == strlen(L[i]) || (ell != m && L[i][ell] < x[ell]))
         d = i;
      else
         f = i;
   }
   *resd = d;
   *resf = f;
}