Please answer following question with Java with extra credit:
Write a program that creates an array of 1000 random numbers in the range 1 - 5000. Then ask the user for a value between and 5000, and search the array until you either find the value or determine that the value is not in the array.
Print a message indicating whether or not the value was found, and how many numbers you had to look at before you found the value (or determined that it was not there).
Using either of the sorting algorithms presented in class, sort your array, then implement the following search algorithm to look for a value requested by the user:
1. Look at the middle value of the array; if the value is found, you're done. Otherwise, the value is either greater or less than this value
2. If the search didn't end in the step above, search the half of the array in which the value must be found (if the value is less than the middle value, search the half from the beginning up to midpoint-1; if the value is greater than the middle value, search from midpoint+1 up to length - 1) using the same method - that is, examine the middle value.
3. Continue the process of dividing the search area in half and examining the midpoint until either the value is found, or you are down to a search area of length 1 which does not contain the value.
4. As with the original search method, your program should report whether or not the value was found, and how many values you had to examine to determine the outcome.