import java.util.Random;
import java.util.Arrays;

public class Search {

  public static int search(int[] arr, int d,
                           int start, int end) {
    
    if(start > end) { return -1; }
    int middle = start + ((end - start) / 2);
    if(d == arr[middle]) { return middle; }
    else if(d < arr[middle]) {
      return search(arr, d, start, middle - 1);
    }
    else { // d > arr[middle]
      return search(arr, d, middle + 1, end);
    }
  }

  public static int search(int[] arr, int d) {
    return search(arr, d, 0, arr.length - 1);
  }


  public static void main(String[] args) {
    int[] a = {0, 1, 2, 2, 5, 6, 6, 8, 9, 9};
    int toFind = 6;
    System.out.println(search(a, toFind));
    int[] arr = randomArray(10);
    System.out.println(Arrays.toString(arr));
    timeSearch(arr);
    timeSearch(arr);
    timeSearch(arr);
  }






  // Return the index where d appears first in arr,
  // or -1 if it isn't contained in arr
  // ASSUME:  arr is in order
  public static int searchLoop(int[] arr, int d) {
    for(int i = 0; i < arr.length; i += 1) {
      if(arr[i] == d) { return i; }
    }
    return -1;
  }

  // Returns a (new) array of the given length containing
  // random integers, in lowest-to-highest order.
  public static int[] randomArray(int length) {
    int[] arr = new int[length];
    Random r = new Random();
    for(int i = 0; i < length; i += 1) {
      arr[i] = r.nextInt(length);
    }
    Arrays.sort(arr);
    return arr;
  }

  // Calculates the amount of time it takes to find
  // a random integer in the given array
  public static void timeSearch(int[] arr) {
    Random r = new Random();
    long start = System.currentTimeMillis();
    int toFind = r.nextInt(arr.length);
    int index = search(arr, toFind);
    long time = System.currentTimeMillis() - start;
    System.out.println(toFind + "\t at \t" + index + "\t of \t" + arr.length + "\t in " + time + "ms");
  }

}