To begin, suppose that you are looking for a particular CD in your collection. After rummaging around for a while with no luck, you may decide to go through the collection systematically, looking at each CD in turn. If you are patient, you will eventually find the one that you are looking for (if it is there).
This simple technique, called a sequential search, can be applied to an array of values.
The following method performs a sequential search on an array of String values for the value called item. If the search is successful, the method returns the index in the array of item but, if the search fails, the method returns -l.
public static int seqSearch (String[] list, String item)
{
int location = -1;
for (int i = 0; i < list.length; i++)
if (list[i] .equals(item))
location = i;
return location;
}
Note that the variable location is initialized to indicate that the search is unsuccessful. If item is not found, this is the value that the method will return. Only if we find item in the list will location be changed.
Although this method works, it is not as efficient as we might wish. Even if it finds item early in the search, it stupidly goes on looking through the rest of the array. We can correct this defect by using a boolean variable that acts as a flag to stop the search as soon as item has been found. We use this device in the next example.
This method shows an efficient implementation of sequential search that quits examining a list immediately after the search has found item.
public static int seqSearch (String[] list, String item)
{
int location = -1;
boolean found = false;
for (int i = 0; i < list.length && !found; i++)
if (list[i] .equals (item))
{
location = i;
found = true;
}
return location;
}
We can achieve even greater efficiency for our sequential search, as shown in the next example.
By eliminating the boolean flag found and the corresponding test in thefor statement to determine the state of found, we can create the followingvery efficientsequential search.
public static int seqSearch (String[] list, String item)
{
for (int i = 0; i < list.length; i++)
if (list[i] .equals(item))
return i;
return -1;
}
Now,if a match for item is ever found, we exit both the for statement and the method immediately. Only if no match is ever found do we complete the for statement and return -1.
Although the code of Example 3 is both simpler and more efficient than that of Example 2, some people still argue that the solution in Example 2 is preferable. In Example 3, the first line of the for statement would make a reader think that the loop is going to be executed for every value in the array but, if a match for item is found, this does not happen. In Example 2, on the other hand, the first line of the for statement is quite clear about what is going to happen - the loop will be executed as long as we haven't reached the end of the array and we haven't found what we are seeking.
3 9 5 7 2 8 4
3 9 7 5 2 8 4