Please use JAVA only to solve following problem: Using either of the sorting alg
ID: 3830224 • Letter: P
Question
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.length;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");
}
}___________________________________
Explanation / Answer
import java.util.*;
public class Lab8Part3 {
public static void main( String[] args ) {
int[] array;
Scanner kb;
// Generate random array
array = new int[1000];
for ( int i = 0; i < array.length; i++ )
array[i] = (int)( Math.random() * 5000 + 1 );
InsertionSort.Sort(array);
kb = new Scanner (System.in);
System.out.print( "Please enter a number between 1 and 5000: " );
int in = kb.nextInt();
System.out.println(in);
int key = BinarySearch.Search(array, in);
if (key == -1)
System.out.println( "Number not found!" );
else
System.out.println( "Found number at index '" + key + "'");
}
}
InsertionSort.java
====
public class InsertionSort {
public static void Sort(int[] array) {
int n = array.length;
for (int j = 1; j < n; ++j) {
int key = array[j];
int i = j - 1;
while ( (i > -1) && (array[i] > key) ) {
array[i + 1] = array[i];
i--;
}
array[i+1] = key;
}
}
}
BinarySearch.java
====
public class BinarySearch {
public static int Search(int[] inputArr, int key) {
int start = 0;
int end = inputArr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
return mid;
}
else if (key < inputArr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
// System.out.println("Start = " + start + ", End = " + end + ", mid = " + mid);
}
return -1;
}
}
Hey there the search algorithm you presented here is not binary search it is linear search. I didn't know which sorting algo your professor taught so I went on with a linear sort. Put all the filenames and stuff accordingly. Works real good!
Cheers,
PrimeHero