10.1 Sequential Search

Searching is a very important task that computers need to do. Often you need to find a particular piece of data. There are many different methods of locating data. Some are much more efficient than others. The examples we'll be looking at will be dealing mostly with Java's primitive types although we'll see later how to deal with objects as well.

Suppose you are looking for the nine of diamonds in a deck of cards. One approach to finding this card (which will work regardless of the order that the cards are in) is to look at each card one at a time until you find the card you want. Eventually you will find your card if it is there. This approach can be extremely time consuming if you are searching through a large number of things. It is reasonably easy to program though. This is called a sequential search.

Example

public class Nine_One
{
   /***********************************
   *  a Sequential Search method
   ************************************/
   public static int seqSearch(double[] list, double item)
   {
      int location = -1;
      for (int i = 0; i < list.length; i++)
         if (list[i] == item)
            location = i;
      return location;
   }

   // This program demonstrates the use of a (non-optimal) sequential search
   public static void main(String[] args)
   {
      double[] nums = {1.1, -9.8, 4.5, 6, -20.7, -18.2, 5.1, 25.25, 19.3, 0.3};
      
      System.out.print("The value -20.7 is ");
      int loc = seqSearch(nums, -20.7);
      if (loc == -1)
         System.out.println("not located in the array.");
      else
         System.out.println("located at position " + loc + " in the array.");
         
      System.out.print("The value 101.1 is ");
      loc = seqSearch(nums, 101.1);
      if (loc == -1)
         System.out.println("not located in the array.");
      else
         System.out.println("located at position " + loc + " in the array.");
   }
}

Generates output of:

The value -20.7 is located at position 4 in the array.
The value 101.1 is not located in the array.

Why do the comments in the code above call this a non-optimal sequential search?

Suppose that the nums array had been defined as:
double[] nums = {1.1, -9.8, 4.5, 6, -20.7, -18.2, 5.1, 25.25, 19.3, 0.3, -20.7, 18.3};
What would seqSearch(nums, -20.7) return?

If the array being searched has 1000 items:
(a) what is the maximum number of items in the list that need to be checked?
(b) what is the minimum number of items?

Here is an improved version of sequential search that stops when you find the item you are looking for.

public static int seqSearch(double[] list, double item) { int location = -1; boolean found = false; // lets us know if we should stop looking for (int i = 0; i < list.length && !found; i++) // see new ending condition if (list[i] == item) { location = i; found = true; // that way we'll get out of the for loop } return location; }