import java.util.ArrayList;

class BinarySearch
{
    //-------------------------//
    // Iterative Binary Search //
    //-------------------------//

    public int iBinarySearch( ArrayList<Integer> list, int key )
    {
        int min = 0, max = list.size() -1;
        
        while( min <= max ) {
            
            int mid = (min + max) / 2;      // find mid index
            
            if( key == list.get(mid) ) {
                return mid;    
            }
            else if( key < list.get(mid) ) {
                max = mid - 1;
            }
            else if( key > list.get(mid) ) {
                min = mid + 1;
            }
            
        }   // end while loop
        
        return -1;        // key not found
    }

    //-------------------------//
    // Recursive Binary Search //
    //-------------------------//

    // Starter method - intialize min to zero & max to the last index
    public int rBinarySearch( ArrayList<Integer> list, int key )
    {
        return rBinarySearch( list, key, 0, list.size()-1 );
    }
  
    private int rBinarySearch( ArrayList<Integer> list, int key, int min, int max )
    {
        if( min > max ) {
            return -1;  // Base case #1 - key not found
        }   
        
        int mid = (min + max) / 2;      // calculate mid point index

        if( key == list.get(mid) ) {    // Base case#2 - found the key
            return mid;
        }
        
        // Recursive case
        if( key < list.get(mid) ) {     // Recursive case#1 - seach lower half
            return rBinarySearch( list, key, min, mid-1 ); 
        }
        else  {                         // Recursive case#2 - search upper half
            return rBinarySearch( list, key, mid+1, max ); 
        }
    }

}