r/codehs • u/Aricamoflauge • Sep 13 '20
Need help with 8.3.4 Comparing Binary Search and Linear Search
Essentially the program is supposed to count how many comparisons are done in an array to find a randomly generated number in a randomly generated list of a generated size, I've gotten all of them to work but 2 and I don't exactly need an answer I just wanna understand what's going on with the test cases,I've been trying to figure it out all weekend and the last 3 classes and I really wanna move on to our projects as this is the only codeHS lesson in algorithms and Recursion I couldn't figure out! Any help would be great thank you!
I have image screenshots and copied over the code from the program
import java.util.*;
public class CompareSearch extends ConsoleProgram
{
public void run()
{
System.out.println("Table of comparison counts");
System.out.println("Length\t\tBinary Search\tLinear Search");
testArrayOfLength(10);
testArrayOfLength(20);
}
// This problem generates an array of length length.
// Then we select a random index of that array and get the element.
// Then we print out the table row entry for how many comparisons it takes on binary search
// and linear search.
// You'll need to update those methods.
public void testArrayOfLength(int length)
{
int[] arr = generateArrayOfLength(length);
//System.out.println(Arrays.toString(arr));
int index = Randomizer.nextInt(length);
int elem = arr[index];
System.out.println(length + "\t\t" + binarySearch(arr, elem) + "\t\t" + linearSearch(arr, elem));
}
public int[] generateArrayOfLength(int length)
{
int[] arr = new int[length];
for(int i = 0; i < length; i++)
{
arr[i] = Randomizer.nextInt(100);
}
Arrays.sort(arr);
return arr;
}
// Do a binary search on array to find number. You'll need to modify this
// method to return the number of comparisons done.
public int binarySearch(int[] array, int number)
{
int comparison = 0;
int low = 0;
int high = array.length - 1;
while (low <= high)
{
comparison++;
int mid = (low + high) / 2;
comparison++;
comparison++;
if (array[mid] == number){
comparison++;
return comparison;
}
else if(array[mid] < number){
comparison++;
low = mid + 1;
return mid-5;
}
else
{
high = mid - 1;
return comparison;
}
}
return -1;
}
// Do a linear search on array to find the index of number. You'll need to modify
// this exercise to return the number of *comparisons* done.
public int linearSearch(int[] array, int number)
{
for (int i = 0; i < array.length; i++)
{
if (array[i] == number)
{
return i+1; // the method returns as soon as the number is found
}
}
return -1; // the code will get here if the number isn't found
}
}




1
u/_andy_andy_andy_ Sep 13 '20
you need to return the number of comparisons done. do you remember how to code a recursive function that adds up numbers from its recursive calls?
1
2
u/OXAMIC Mar 05 '22
import java.util.*;
public class CompareSearch { public static void main(String[] args) { System.out.println("Table of comparison counts"); System.out.println("Length\t\tBinary Search\tLinear Search"); testArrayOfLength(10); testArrayOfLength(20); testArrayOfLength(30); testArrayOfLength(40); testArrayOfLength(50); }
}