Please use JAVA only to solve following problem:

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.

Here"s code below for Binary Search:

import java.util.*;

public class Lab8part3

{

public static void main (String [] args)

{

// populate array

int [] array = new int [ 1000];

for ( int i = 0;i

array [i] = (int) (Math.random()*5000+ 1);

}

// get inout from user

Scanner kb= new Scanner (System.in);

System.out.print(" please enter a number between 1 and 5000: " );

int input = kb.nextInt();

// search for input in the array

for (int i = 0; i < array.length;i++){

if (array[i] == input){

System.out.println("we found "+ input + " at index " + i );

System.exit(0);

}

}

System.out.println (" number is not found in array");

}

}___________________________________