public static int  search(int[]  arr, int  key)  {
  int  i = 0;
  while (i < arr.length && arr[i] != key)  {
    ++i;
  }
  return  i == arr.length ? -1 : i;
}

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

Initial call: 
binarySearch(arr,12,0,10) 
    middle = 5
    compare 12 to middle element arr[5], 9:
    12 is larger, ignore bottom half
    find 12 in [12, 15, 16, 32, 45] by calling
    binarySearch(arr,12,6,10) 
        middle = 8  
        compare 12 to middle element arr[8], 16:
        12 is smaller, ignore top half
        find 12 in [12, 15] by calling
        binarySearch(arr,12,6,7) 
          middle = 6 
          compare 12 to middle element arr[6], 12:
          MATCH and return 6