Question after this code: import javax.swing.JOptionPane; /** * Class that demon

Question

Question after this code:

import javax.swing.JOptionPane;

/**
* Class that demonstrates search algorithms
*
**/
public class Searcher
{

/**
* Implement a linear search through the list
**/
public static String linearFind(String target, String[] list)
{
for (int index=0; index < list.length; index++)
{
if (target.compareTo(list[index]) == 0)
{return("Found it!"); }
}
return("Not found");
}
  
/**
* Method to use a binary search to find a target string in a
* sorted array of strings
*/
public static String binaryFind(String target, String[] list)
{
int start = 0;
int end = list.length - 1;
int checkpoint = 0;

while (start <= end)
{ //While there are more to search
// find the middle
checkpoint = (int)((start+end)/2.0);
System.out.println("Checking at: "+
checkpoint+" start="+start+" end="+end);
if (target.compareTo(list[checkpoint]) == 0)
{
return "Found it!";
}
else if (target.compareTo(list[checkpoint]) > 0)
{
start=checkpoint + 1;
}
else if (target.compareTo(list[checkpoint]) < 0)
{
end=checkpoint - 1;
}
}
return "Not found";
}
  
/** main for testing linearFind */
  
public static void main(String[] args)
{
String[] searchMe = {"apple","bear","cat","dog","elephant"};
// note the use of an input dialog box. What type of data does it return to us?
String term = JOptionPane.showInputDialog("what do you want to search for?");
// note the use of a message dialog box
JOptionPane.showMessageDialog(null,term + " - " + linearFind(term,searchMe));
// can you replace the hard coded search values in the
// next 2 statements using input dialog boxes?
JOptionPane.showMessageDialog(null,linearFind("cat",searchMe));
JOptionPane.showMessageDialog(null,linearFind("giraffe",searchMe));

}
  

/**
* Main for testing binary find
*/
/*
public static void main(String[] args)
{
String[] searchMe = {"apple","bear","cat","dog","elephant"};
System.out.println(binaryFind("apple",searchMe));
System.out.println(binaryFind("cat",searchMe));
System.out.println(binaryFind("giraffe",searchMe));
}
*/
}

////////////

In order to better understand how the linear and binary search algorithms perform their tasks, we are going to ‘walk through’ (describe step by step) an example of each.

Using the Searcher.java logic posted, describe what happens when the following code is executed:

1.String[] searchMe = {"apple","bear","cat","dog","elephant"};

2.System.out.println(linearFind("cat",searchMe));

3.System.out.println(binaryFind("apple",searchMe));

In addition to describing the results of each of these statements, make sure you describe the details of what happens in each of the methods that are called: when is the loop condition checked, what are the values of the local variables and when do they change, at what point do we return from each method, and what data gets returned?

Explanation / Answer

1. Firstly, a String array is created i,e., String[] searchMe = {"apple","bear","cat","dog","elephant"};

2. Here a print statement is written calling the method linearFind() and passing a String value and the previously defined String array i.e., "cat" and searchMe[], respectively.

Explanation

Now, when linearFind() method is called with passing the above mentioned parameters, then program control moves to the following method assigning "cat" to variable target and searchMe[] to list[] to the method respectively.

public static String linearFind(String target, String[] list)
{
for (int index=0; index < list.length; index++)
{
if (target.compareTo(list[index]) == 0)
{return("Found it!"); }
}
return("Not found");
}

The program control comes at for loop. Making index=0 , and assigning a executing condition index<length of list (here list is the same SearchMe[] array passed at parameters during method call. Now in the for body the target i.e., the "cat" which was passed to method during its call, is searched with each index position of the list[] array .The searching is done in body of 'if' statement and if its found then program, exits from loop and method returns the value "Found it", and if its not found then simply it returns "Not Found".

1st execution -> list[0] = "apple " != cat => Comparison fails

2nd execution -> list[1] = "bear" != cat => Comparison fails

3rd execution -> list[2] = "cat " == cat => Comparison succeeds and method returns value "Found it" and loop is terminated

3. System.out.println(binaryFind("apple",searchMe));

Explanation

In above statement a print statement is wrtiten calling the method binaryFind() and passing the String to be searched and the list of Strings i.e., "apple" and searchMe as parameter of method respectively.

Now, the program control goes to the method binaryFind() and "apple" is assigned to variable target and searchMe[] array is assigned to list[]. Now come to body part of method binaryFind().

int start = 0;
int end = list.length - 1;
int checkpoint = 0;

a variable start is declared with value 0, end is declared with length of of list -1 because index is always 1 less then the position of actual values in an array. And checkpoint is intialized with 0. Now come to while loop.

while (start <= end)
{ //While there are more to search

// find the middle
checkpoint = (int)((start+end)/2.0);
System.out.println("Checking at: "+
checkpoint+" start="+start+" end="+end);
if (target.compareTo(list[checkpoint]) == 0)
{
return "Found it!";
}
else if (target.compareTo(list[checkpoint]) > 0)
{
start=checkpoint + 1;
}
else if (target.compareTo(list[checkpoint]) < 0)
{
end=checkpoint - 1;
}
}
return "Not found";
}

In while loop body the condition is mentioned to iterate to through the condition as long as index start is less then index end. Checkpoint is always changing to value to half of sum start and end at each loop iteration. And there is a print statement to print the current start and end index at console on each loop iteration.

1st iteration -> checkpoint = [ 0+4 ] / 2 = 2.

so string is compared to value of list at index 0 at first if condition , if its found then target.compareTo(list[checkpoint]) return 0  and function returns value "Found it".

Otherwise control goes to next if condition and compares if value(entered string) at that checkpoint is greater then 0 if yes, then value of start becomes checkpoint+1 = 2+1 = 3.

if value at above checkpoint is not greater then 0 (i.e., value is less then 0) then value of end becomes checkpoint - 1 = 4-1 = 3.

and then loop executed 2nd time.

and value of checkpoint is updated with new start and end value. i.e., checkpoint=3+3 / 2 = 3

and process is repeated by executing the loop till the value of checkpoint becomes 2. And when the value of checkpoint becomes 2 the entered string is matched with target.compareTo(list[checkpoint]) ==list[2] == "cat"==0. And the method returns "Found it". and hence loop terminates.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.