10.3. Linear Searching¶

In this section, we’ll take a look at how to search for a value in an array. Although a fairly straightforward topic, it is one that comes up repeatedly in programming.

10.3.1. Linear Search¶

By far, one of the most common searches you will see in typical programs. It also happens to be one of the more misused searches, which is another reason we want you to know about it.

Here is the code from example searching/searching.cs to perform a linear search for an integer in an array:

      /// Return the index of the first position in data
      /// where item appears, or -1 if item does not appear.
      public static int IntArrayLinearSearch(int[] data, int item)
      {
         int N=data.Length;
         for (int i=0; i < N; i++) {
            if (data[i] == item) {
               return i;
            }
         }
         return -1;
      }

Here’s what it does:

In lines 5-6 we set up a loop to go from 0 to N-1. We often use N to indicate the size of the array (and it’s much easier to type than data.Length.
In line 7, we see whether we found a match for the item we are searching. If we find the match, we immediately leave the loop by returning the position where it was found.
It is worth noting here that the array, data, may or my not be in sorted order. So our search reports the first location where we found the value. It is entirely possible that the more than one position in the array contains the matching value. If you wanted to find the next one, you could modify the IntArrayLinearSearch() method to have a third parameter, start, that allows us to continue searching from where we left off. It might look something like the following:

      /// Return the first index >= start in data where
      /// item appears, or -1 if item does not appear there.
      public static int IntArrayLinearSearch(int[] data, int item,
                                             int start)
      {
         int N=data.Length;
         if (start < 0) {
            return -1;
         }
         for (int i=start; i < N; i++) {
            if (data[i] == item) {
               return i;
            }
         }
         return -1;
      }
   }
}

The following code in Main of searching/searching_demo.cs demonstrates how to use the linear search:

         string input = UI.PromptLine(
            "Please enter integers, separated by spaces and/or comma: ");
         int[] data = ExtractFromString.IntsFromString(input);
         for (int i=0; i < data.Length; i++) {
            Console.WriteLine("data[{0}]={1}", i, data[i]);
         }
         string prompt =
            "Please enter a number to find (blank line to end): ";
         input = UI.PromptLine(prompt);
         while (input.Length > 0) {
            int searchItem = int.Parse(input);
            int searchPos = UI.PromptIntInRange(
                               "At what position should the search start? ",
                               0, data.Length);
            int foundPos =
               Searching.IntArrayLinearSearch(data,searchItem, searchPos);
            if (foundPos < 0) {
               Console.WriteLine("Item {0} not found", searchItem);
            }
            else {
               Console.WriteLine("Item {0} found at position {1}",
                                 searchItem, foundPos);
            }
            input = UI.PromptLine(prompt);
         }

In this example, we ask the user to enter all the data for the array on one line. To convert the string to an int array we use the result of the IntsFromString Exercise that we put in searching/extract_from_string.cs.

To allow easy termination of the testing loop, we do not use PromptInt for searchItem, because any int could be the search target. By using PromptLine, we can allow an empty string as the response, and we test for that to terminate the loop.

The rest is mostly self-explanatory.