// Your job is to build methods 1-3 at the bottom of this class. You do not need to modify main at all.

public static void main(String[] args) {

// any values over ~2.1 million need to be stored as LONGs and not INTs.

// unfortunately arrays are indexed with INT so they can only have up to 2.1million elements in them

// next week we will cover how to store more than 2.1 million elements

final int SIZE = 2 * 1000 * 1000; // two million numbers

System.out.println("Creating array of " + SIZE + " random numbers");

Random rand = new Random();

int[] numbers = new int[SIZE];

for(int i=0; i < SIZE; i++) {

numbers[i] = rand.nextInt(SIZE); // add a random int between 0 and SIZE to the array

}

System.out.println("Now sorting the array..");

sortArray(numbers);

int key = numbers[rand.nextInt(SIZE)];

System.out.println("Now searching for the number " + key + " in the array");

long linearStart = System.currentTimeMillis();

int idx = linearSearch(numbers, key);

long linearEnd = System.currentTimeMillis();

System.out.println("Linear search took " + (linearEnd - linearStart) + " milliseconds");

long binaryStart = System.currentTimeMillis();

idx = binarySearch(numbers, key);

long binaryEnd = System.currentTimeMillis();

System.out.println("BinarySearch took " + (binaryEnd - binaryStart) + " milliseconds");

}

// 1) the sortArray method calls the Arrays sort method to sort nums. It doesn't need to return anything as nums is sorted in place.

// 2) the binarySearch method calls the Arrays binarySearch method, which returns the index of the key we are searching for.

// 3) the linearSearch method loops through the array, looking for the index of a specified key. If the key is not found, return -1

// you must write this method yourself.

}