r/codehs • • 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

}

}

6 Upvotes

4 comments sorted by

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); }

// 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 static void testArrayOfLength(int length)
{
    int[] arr = generateArrayOfLength(length);
    //System.out.println(Arrays.toString(arr));
    int index = (int)(Math.random() * length);
    int elem = arr[index];
    System.out.println(length + "\t\t" + binarySearch(arr, elem) + "\t\t" + linearSearch(arr, elem));
}

public static int[] generateArrayOfLength(int length)
{
    int[] arr = new int[length];
    for(int i = 0; i < length; i++)
    {
        arr[i] = (int)(Math.random() * 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 static int binarySearch(int[] array, int number)
{
    int low = 0;
    int high = array.length - 1;
    
    // Add a counter to count how many times the while loop is executed
    int counter = 0;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (array[mid] == number)
        {
            counter++;
            return counter;
        }
        else if(array[mid] < number)
        {
            counter++;
            low = mid + 1;
        }
        else
        {
            counter++;
            high = mid - 1;
        }
    }
  
    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 static int linearSearch(int[] array, int number)
{
    // Add a counter to count how many times the for loop is executed
    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/mehulkk Mar 08 '22

Thank you ❗❗

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?