I have a program that searches an array of 10 elements for a target from the beginning of the array to the end of the array and then from the end of the array to the beginning of the array. Each time the program is run the array of Strings is shuffled.
I'm clocking the time it takes to find the target for both searches. What I'm finding is that the search from the end of the array to the beginning is always fastest, even if the target is located at the 0 position in the array.
Can someone explain why this is happening?
Here is my program:
public class LinearStringSearch {
// Array filled with random Strings
String[] randomStrings = {"apple", "yellow", "fire", "wood", "zinc",
"ram", "mouse", "fish", "cheese", "dirt"};
// Save target arguments for global access(console printing purposes)
String target;
String target2;
long startTime;
long startTime2;
long estimatedTime;
long estimatedTime2;
/**
*
* @param target - the item you want to retrieve from array
* @param sa - the name of the array
* @return i - the target, otherwise return error code: -1
*/
int linearStringSearch(String target, String[] sa) {
this.target = target; // set class variable for print access
shuffleArray(sa);
startTime = System.nanoTime(); // Start speed test
for(int i = 0; i < sa.length; ++i) {
//System.out.println("Searching array position: " + i); // Comment out for more accuracy
if (sa[i].equals(target)) {
estimatedTime = System.nanoTime() - startTime; // End speed test
System.out.println("The target " + "'" + target + // Print target/index to console
"'" + " found at array index: "+ i);
System.out.println("Estimated search time in " + // Print estimated time
"nanoseconds: " + estimatedTime);
return i; // return the index of target
}
}
return -1; // -1 means that target was not found
}
/**
*
* @param target - the item you want to retrieve from array
* @param sa - the name of the array
* @return i - the target, otherwise return error code: -1
*/
int backwardLinearStringSearch(String target, String[] sa) {
this.target2 = target; // set class variable for print access
startTime2 = System.nanoTime(); // Start speed test
for(int i = 9; i < sa.length; --i) {
//System.out.println("Searching array position: " + i); // Comment out for more accuracy
if (sa[i].equals(target)) {
estimatedTime2 = System.nanoTime() - startTime2; // End speed test
System.out.println("The target " + "'" + target2
+ "'" + " found at array index: " + i); // Print to console
System.out.println("Estimated search time in " + // Print estimated time
"nanoseconds: " +estimatedTime2);
return i; // return the index of target
}
}
return -1; // -1 means that target was not found
}
/**
*
* @param estimatedTime - estimated time of search beginning to end
* @param estimatedTime2 - estimated time of search end to beginning
* @return fastest method
*/
String deduceFastestSearchMethod(long estimatedTime, long estimatedTime2) {
if(estimatedTime < estimatedTime2) {
return "linearStringSearch found " + "'"
+ target + "'" + " fastest";
}
return "backwardLinearStringSearch found " +
"'" + target + "'" + " fastest";
}
// Implement Fisher–Yates shuffle
public void shuffleArray(String[] sa){
Random rnd = new Random();
for (int i = sa.length - 1; i > 0; i--){
int index = rnd.nextInt(i + 1);
// Simple swap
String a = sa[index];
sa[index] = sa[i];
sa[i] = a;
}
}
/*
* The target string is searched from the beginning of the array to the end of the array, then
* from the end of the array to the beginning of the array.
*
*/
public static void main(String[] args) {
LinearStringSearch lss = new LinearStringSearch();
// Search array from beginning to end
System.out.println("Linear search: "); // Print title
lss.linearStringSearch("mouse", lss.randomStrings); // Pass arguments
// Search array from end to beginning
System.out.println("\nBackwards linear search: "); // Print title
lss.backwardLinearStringSearch("mouse", lss.randomStrings); // Pass arguments
// Print fastest search
System.out.println();
System.out.println(lss.deduceFastestSearchMethod(lss.estimatedTime, lss.estimatedTime2));
}
}
Here is a test output:
Linear search:
The target 'mouse' found at array index: 0
Estimated search time in nanoseconds: 9058
Backwards linear search:
The target 'mouse' found at array index: 0
Estimated search time in nanoseconds: 4982
backwardLinearStringSearch found 'mouse' fastest
Here is another test output:
Linear search:
The target 'mouse' found at array index: 8
Estimated search time in nanoseconds: 12229
Backwards linear search:
The target 'mouse' found at array index: 8
Estimated search time in nanoseconds: 3170
backwardLinearStringSearch found 'mouse' fastest