package array;
  
  public class BinarySearch {
  
    static boolean binarySearch(int[] a, int v) {
      int lo = 0, hi = a.length; // on cherche dans [lo..hi[
      while (lo < hi) {
        int m = lo + (hi - lo) / 2;
        if (a[m] == v)
          return true;
        if (a[m] < v)
          lo = m + 1;
        else
          hi = m;
      }
      return false;
    }
    
    // une version générique
    // renvoie la position où l'élément se trouve / devrait être inséré
    
    static<E extends Comparable<E>> int binarySearch(E[] a, E v) {
      return binarySearch(a, v, 0, a.length);
    }
    
    // le code ci-dessous cherche dans l'intervalle ouvert [lo..hi[
    
    static<E extends Comparable<E>> int binarySearch(E[] a, E v, int lo, int hi) {
      while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int c = a[mid].compareTo(v);
        if (c == 0)
          return mid;
        if (c < 0)
          lo = mid + 1;
        else
          hi = mid;
      }
      return lo;
    }
  
  }
  
  class TestBinarySearch {
    public static void main(String[] args) {
    	int[] a = {1, 2, 3, 5, 10};
    	assert !BinarySearch.binarySearch(a, 0);
    	assert BinarySearch.binarySearch(a, 1);
    	assert BinarySearch.binarySearch(a, 3);
    	assert !BinarySearch.binarySearch(a, 4);
    	assert BinarySearch.binarySearch(a, 10);
    	assert !BinarySearch.binarySearch(a, 11);
    	Integer[] b = {1, 2, 3, 5, 10};
    	assert BinarySearch.binarySearch(b, 0) == 0;
    	assert BinarySearch.binarySearch(b, 1) == 0;
    	assert BinarySearch.binarySearch(b, 3) == 2;
    	assert BinarySearch.binarySearch(b, 4) == 3;
    	assert BinarySearch.binarySearch(b, 10) == 4;
    	assert BinarySearch.binarySearch(b, 11) == 5;
      // System.out.println(BinarySearch.binarySearch(new Integer[] { 1,1,3 } , 1));
    }
  }