12.3. Searching

In this section, we’ll take a look at how to search for a value in an array. You will learn about linear search and binary search.

Note

namespace

Note that to use the example files downloaded from GitHub, you need to keep the namespace consistent. It is recommended to use IntroCSCS (or IntroCS) and you have to check every file to make sure they are consistent. Failing to do so will incur an error “error CS0103: The name ‘CLASS’ does not exist in the current context”.

12.3.1. Linear Search

Although a fairly straightforward topic, linear search is one that comes up repeatedly in programming. Linear search is 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 you want to know about it.

Note

You need to download several files in the GitHub introcs-csharp-examples/searching/ directory to successfully run the linear search operations: searching.cs, extract_from_string.cs, searching_demo.cs, in addition to ui.cs.

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:

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 IntsFromString() method in class ExtractFromString 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.

12.3.2. Binary Search

Binary search is an improvement over linear searching that works only if the data in the array are sorted beforehand.

Suppose we have the following array data shown under the array indices:

10  20  30  40  50  60  70  80  90  100 115 125 135 145 155 178 198

Binary search works by keeping track of the midpoint (mid) and the minimum (min) and maximum (max) index positions where the item might be.

If we are looking for a number, say, 115, here is a visual on how we might go about it. We display the indices over the data being considered. Here min and max are the smallest and largest index to still consider. A textual explanation follows the visual:

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
  10  20  30  40  50  60  70  80  90 100 115 125 135 145 155 178 198
min=0 max=16 mid=8
                                     100 115 125 135 145 155 178 198
min=9 max=16 mid=12
                                     100 115 125
min=9 max=11 mid=10
Item 115 found at position 10

We start by testing the data at position 8. 115 is greater than the value at position 8 (100), so we assume that the value must be somewhere between positions 9 and 16.
In the second pass, we test the data at position 12 (the midpoint between 9 and 16). 115 is less than the value at position 12, so we assume that the value must be somewhere between positions 9 and 11.
In the last pass, we test the value at position 10. The value 115 is at this position, so we’re done.

So binary search (as its name might suggest) works by dividing the interval to be searched during each pass in half. If you think about how it’s working here with 17 items. Because there is integer division here, the interval will not always be precisely half. it is the floor of dividing by 2 (integer division, that is).

With the data above, you see that the algorithm determined the item within 3 steps. To reduce to one element to consider, it could be 4 or 5 steps. Note that \(4 < log_2 17 < 5\).

Now that we’ve seen how the method works, here is the code in binary_searching/binary_searching.cs that does the work:

/// Return the index of item in a non-empty sorted array data,
/// or return -1 if item is not in the array.
public static int IntArrayBinarySearch(int[] data, int item)
{
   int min = 0, max = data.Length-1;
   while(min <= max) {
      int mid = (min+max) / 2;
      if (data[mid] == item)
         return mid;
      if (item > data[mid])
         min = mid + 1;
      else
         max = mid - 1;
   }
   return -1;
}

Here’s a quick explanation, because it largely follows from the above explanation.

Line 5: Initially item could be anywhere in the array, so minimum is at position 0 and maximum is at position N-1 (data.Length - 1).
The loop to make repeated passes over the array begins on line 6. We can only continue searching if there is some data left to consider (min <= max).
Line 7 does just what we expect: It calculates the median position (mid).
It is always possible that we’ve found the item, which is what we test on line 8, and return with our answer if we found it.
Lines 10-13: If not, we continue. If the item is greater than the value at this mid position, we know it is in the “upper half”. Otherwise, it’s in the “lower half”.
Line 15: Otherwise the binary search loop terminates, and we return -1 (to indicate not found). The -1 value is a commonly-returned indicator of failure in search operations (especially on arrays, lists, and strings), so we use this mostly out of respect for tradition. It makes particular sense, because -1 is not within the index set of the array (which starts at 0 in C# and ends at data.Length - 1.

Of course we generally would be searching in an array with multiple elements. It is still important to check edge cases: Check that the code correctly returns -1 if the array has length 0 (a legal length).

Similar to linear searching, we provide a main program that tests it out in binary_searching/binary_searching_demo.cs. It uses an elaboration of binary search that prints out the steps visually, as in the introduction to this section. It also references previous example projects: functions from files searching/extract_from_string.cs and sorting/sorting.cs.

   string input = UI.PromptLine(
      "Please enter some comma/space separated integers: ");
   int[] data = ExtractFromString.IntsFromString(input);
   Sorting.IntArrayShellSortBetter(data);
   string prompt =
      "Please enter a number to find (empty line to end): ";
   input = UI.PromptLine(prompt);
   while (input.Length != 0) {
      int searchItem = int.Parse(input);
      int foundPos = BinarySearching.IntArrayBinarySearchPrinted(
                        data, searchItem);
      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);
   }