package binarysearch;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class BinarySearch {

    public static int comparisons = 0;

    public static List<Integer> makeList( int size ) {
        List<Integer> result = new ArrayList<>();

        for( int i = 0; i < size; i++ ) {
            int evenInteger = 2 * (i + 1);
            result.add( evenInteger );
        } // for

        return result;
    } // makeList( int )

    public static void printList( List<Integer> data ) {
        int count = 0;
        for( int n : data ) {
            System.out.printf( "%4d ", n );

            if( (count + 1) % 12 == 0 ) {
                System.out.println();
                count = 0;
            } // if
            else {
                count++;
            } // else
        } // for
    } // printList( List<Integer> )

    public static boolean search( int value, List<Integer> data ) {
        return searchHelper( value, data, 0, data.size() - 1 );
    } // search( int, List<Integer> )

    public static boolean searchHelper( int value, List<Integer> data,
            int loIndex, int hiIndex ) {

        assert loIndex < 0 || hiIndex >= data.size() || loIndex > hiIndex :
            "indices are out of bounds";
        
        if( loIndex == hiIndex ) {
            if( data.get(loIndex) == value ) {
                return true;
            } // if
            else {
                return false;
            } // else
        } // if
        else if( hiIndex - loIndex == 1 ) {
             if( data.get(hiIndex) == value || data.get(loIndex) == value ) {
                 return true;
             } // if
             else {
                 return false;
             } // else
        } // else if
        else {
            int middleIndex = (loIndex + hiIndex)/2;
            if( data.get(middleIndex) == value ) {
                return true;
            } // if
            else if( data.get(middleIndex) >  value ) {
                return searchHelper( value, data, loIndex, middleIndex );
            } // else if
            else {
                return searchHelper( value, data, middleIndex, hiIndex );
            } // else 
        } // else

    } // searchHelper( int, List<Integer>, int, int )

    public static void main( String [] args ) {
        int size = 24;
        List<Integer> data = makeList( size );
        printList( data );

        Random rng = new Random();

        for( int i = 0; i < 50; i++ ) {
            System.out.println( i + " was found: " + search(i, data) );
        } // for
    } // main( String [] )

} // BinarySearch