#include <stdio.h>
#include <stdlib.h>

// Recherche x dans t entre les positions i et j (comprises)
// L'invariant suivant est maintenu entre les appels récursifs: soit i et j sont des indices légaux dans t, soit i > j.
int dicho(int t[], int i, int j, int x)
{
  if (i > j) {
    return -1;
  }
  int middle = (i+j)/2;
  if (x == t[middle]) {
    return middle;
  }
  if (x < t[middle]) {
    return dicho(t, i, middle-1, x);
  }
  return dicho(t, middle+1, j, x);
}

int dichotomic_search(int t[], int n, int x)
{
  return dicho(t, 0, n-1, x);
}

void test(int t[], int a, int b)
{
  printf("%d\n", dichotomic_search(t, a, b));
}


int main(void)
{
  int t[] = {0,1,2,3,4,5,6,7,8,9,10};

  for (int i=0; i < 12; ++i) {
    test(t, 11, i);
  }
  return EXIT_SUCCESS;
}

// dicho.c ends here