import java.util.Random;

public class Homework
{

    static final int SORTED_ARRAY_SIZE = 20000;
    static final int[] sorted_array = new int[SORTED_ARRAY_SIZE];
    /*
     * Return the index of the target or -1 if not found.
     */
    public static int binarySearch(int [] element, int target){
        int start = 0;
        int end = sorted_array.length -1;
        int halfway = (end - start) / 2;

        for (int x = 0; x < sorted_array.length; x++){
            if(sorted_array[x] == target){
                return x;
            }
            else if(sorted_array[halfway] > target){
                    end = halfway -1;
            }
            else {
                start = halfway + 1;
            }

        }
        return -1;
    }

    /*
     * Return the index of the target or -1 if not found.
     */
    public static int sequentialSort(int[] element, int target) {
        for (int x = 0; x < sorted_array.length; x++)
      {
         if (sorted_array[x] == target)
         {
            return x;
         }
     }
     return -1;

    }


    public static void main(String[] args)
    {

        int[] sorted_array = new int[SORTED_ARRAY_SIZE];

        for(int i = 0; i < SORTED_ARRAY_SIZE; i++)
        {
            sorted_array[i] = i*2;
        }

        Random rand = new Random();
        int[] random_array = new int[SORTED_ARRAY_SIZE];

        for(int i = 0; i < SORTED_ARRAY_SIZE; i++)
        {
            random_array[i] = rand.nextInt(200000);

        }

        System.out.println(binarySearch(sorted_array,458));
        System.out.println(binarySearch(sorted_array, 19887));
        System.out.println(binarySearch(sorted_array, -90));

        System.out.println(sequentialSort(random_array, 9983));
        System.out.println(sequentialSort(random_array, 199327));
        System.out.println(sequentialSort(random_array, 22873));
        System.out.println(sequentialSort(random_array, 723625));




    }

}