Please answer following question with Java with extra credit : (5 points) Write
ID: 3822749 • Letter: P
Question
Please answer following question with Java with extra credit:
(5 points) 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). • Search Counter ____________________________________
Extra credit option for part 3: 5 points 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.
• Binary Search: ___________________________________
Explanation / Answer
import java.util.*;
class Array
{
int y = 5000;
int x;
int values[] = new int[1000];
Array()
{
Random rg = new Random();
for (int x=0;x<values.length;x++)
values[x]=rg.nextInt(y+1);
Arrays.sort(values);
}
public int findNumber(int val)
{
int s=0, r = values.length;
int x=0;
while(true)
{
x++;
if (values[(r+s)/2]==val)
return x;
else if (val > values[(r+s)/2])
s = (r+s)/2 + 1;
else
r = (r+s)/2 - 1;
if (s>r)
return -1;
}
}
public static void main(String[] args)
{
Array fN = new Array();
Scanner kb = new Scanner(System.in);
System.out.println("Enter between 1 and 5000.");
int a = kb.nextInt();
if (fN.findNumber(a)>0)
System.out.println("Found in " + fN.findNumber(a) + " tries.");
else
System.out.println("Value not found!");
}
}