Todo

This is completely in draft mode now and is at best in placeholder status. No revisions please.

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.

These examples make use of arrays and loops, not to mention functions (for putting it all together). You’ll also begin to see greater use of the return statement and return values (the results of functions).

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 to perform a linear search for an integer in an array:

      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 2-3 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 4, we are checking whether data[i] == item. What this is telling us is 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:

      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 shows how to use the linear search:

      public static void Main (string[] args)
      {
         Console.WriteLine ("Please enter some integers, separated by spaces:");
         string input = Console.ReadLine();
         string[] integers = input.Split(' ');
         for (int i=0; i < integers.Length; i++)
            Console.WriteLine("i={0} integers[i]={1}", i, integers[i]);
         int[] data = new int[integers.Length];
         for (int i=0; i < data.Length; i++)
            data[i] = int.Parse(integers[i]);

         for (int i=0; i < data.Length; i++)
            Console.WriteLine("i={0} data[i]={1}", i, data[i]);

         while (true) {
            Console.WriteLine("Please enter a number you want to find (blank line to end):");
            input = Console.ReadLine();
            if (input.Length == 0)
               break;
            int searchItem = int.Parse(input);
            Console.WriteLine("Please enter a position to start searching from (0 for beginning): ");
            input = Console.ReadLine();
            int searchPos = int.Parse(input);
            int foundPos = 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);
         }
      }
   }
}

In this example, we ask the user to enter an array of data by entering the values one at a time. As we’ve learned before, Console.ReadLine() gives us a string, which we can then split using the Split() method. (It is important that the items in this array are only separated by a single space character as Split() is not flexible to handle extra spaces.

Once we have gotten the input text split into an array of string (string[]), we set up a simple loop (on lines 7-8) to convert each item in the string array into an integer.

The rest is mostly self-explanatory.