/** RICERCA BINARIA
 * 
INVARIANTE:

inf >= 0
AND
sup <= a.length - 1
AND
se x è presente in a allora è presente
nella porzione a[inf ... sup],
cioè da inf a sup (inclusi).

*/
/** ricerca binaria, restituente un booleano */
  public static boolean ricercaBin(int x, int[] a) {
    int i, inf = 0, sup = a.length - 1;
    while(inf <= sup) {
      i = (inf + sup)/2;
      if(x < a[i]) sup = i-1;
      else if(x > a[i]) inf = i+1;
      else return true;
    }
    return false;
  }

/** ricerca binaria, restituente l'indice */
  public static int ricercaBin(int x, int[] a) {
    int inf = 0, sup = a.length - 1;
    if(sup == -1 || x < a[0] || x > a[sup]) return -1;
    while(inf <= sup) {
      int i = (inf + sup)/2;
      if(x < a[i]) sup = i-1;
      else if(x > a[i]) inf = i+1;
      else return i;
    }
    return -1;
  }


/** FUSIONE ORDINATA (MERGE) DI DUE ARRAY ORDINATI

 presi come argomenti due array ordinati (che possono contenere elementi ripetuti),
    crea e restituisce un nuovo array ordinato (eventualmente contenente elementi ripetuti)
    dato dalla fusione ordinata
    dei due array-argomenti (senza modificare tali array-argomenti)
 */
  public static int[] fondi(int[] a, int[] b) {
    int m = a.length;
    int n = b.length;
    int[] c = new int[m+n];

    int i = 0, j = 0;
    while(i < m && j < n) {
      if(a[i] <= b[j]) {
        c[i+j] = a[i];
        i++;
      }
      else {
        c[i+j] = b[j];
        j++;
      }
    }
    while(i < m) {
      c[i+j] = a[i];
      i++;
    }
    while(j < n) {
      c[i+j] = b[j];
      j++;
    }
    return c;
  }