Arrays: Linear Search Through An Array (For Loop)

References:

• Pre-requisite: it is assumed that you have read through the prior tutorials, and are familiar with the concepts covered in those tutorials.

Goals:

• In this tutorial, we will:
  • Examine how two variations of a 'linear search' works, using an array.

1. Obtain the example code

• Here is the zip file to the source files and compiled executable of this example.
• Here is the keyboard mapping for the XBOX 360 controller.  
• Here is the main tutorial page for working with XNACS1Lib, and here is the complete documentation of the library: html-page or compiled html help file.

In this tutorial, you can control the location of the soccer ball using the right thumbstick.  At the top of the screen, the contents of an array of numbers is displayed (in this case, the array holds the values 2, 3, 7, and 9).  If the soccer ball  isn't overlapping with any blocks, then the message "No Number To Search For!" is displayed at the bottom of the screen, as pictured here:

 If the soccer ball overlaps with a block, then the program figures out what number is on the block, and looks through the array of numbers to try and find the block's number.  If the program finds the block's number in the array, then the "Found the value X in the array!" is displayed at the bottom of the screen (where X is the block's number), as pictured here:

If the program finds the block's number in the array, then the "X was not found in the array!" is displayed at the bottom of the screen (where X is the block's number), as pictured here:

The major new concept for this tutorial has less to do with C# syntax, semantics, or techniques, and more to do with clearly identifying a pattern that programmers frequently use: a linear search. 

Arrays are used to store a collection of things, which we may then need to locate again later.  Whether those things are numbers, such as employee ID numbers or prices, or whether those things are objects, like on-screen rectangles, isn't really important for the purposes of doing  linear search.  What is important is that we will frequently need to determine if a particular object (or number) is in the array (collection), based on some criteria.  As an example, let's say that we have an array of the employee ID numbers for employees who are on vacation.  Let's say that we want to know if someone is on vacation (let's call him Joe), and we have their employee ID number.  One way to see if Joe's employee ID number is in the array is to simply start with element 0, and ask "Is this Joe's ID number?"  If it is, then we know Joe is on vacation (and we can stop our search).  If not, then we go on to element #1, and again ask "Is this Joe's ID number?"  If it is, then we know Joe is on vacation (and we can stop our search).  If not, then we go on to element #2, and ask the same question again.  If Joe's ID number is anywhere in the array, then we will eventually find it.  If Joe's number is NOT in the array, then we will traverse the entire array, find that it's not there, and conclude that Joe's number is not in the array.

This technique is called a 'linear search' for at least a couple of reasons:

1. The time required to search the array is directly proportional to the number of elements in the array.  If it takes the computer, say, 15 units of time (don't worry about the units - maybe it's seconds, maybe it's milliseconds - it doesn't actually matter), then searching 10 elements will take (10*15=) 150 units of time.  Searching 100 elements will take (100*15=)1500 units of time.  In a nutshell, (time required) = 15 * (number of elements).  If we translate this into a mathematical formula, and say that (time required) is y, and (number of elements) is x, then we get the equation y = 15x, which is clearly a linear equation.  Thus, we call this search technique a linear search because it will require linear time, as a function of the number of array elements. 
       For now, don't worry about the details of this - you will see these concepts again later, but don't really need to understand them in detail right now.  

2. You can think about the linear search as starting at one end of the array, and then stepping through the array, as if it was following the blue line in the following picture:
   
   In this tutorial, we'll examine two ways in which you can use the 'linear search' idea: first, to find an object in an array that satisfies some criteria (in this case, "Does the soccer ball overlap the block?"), and second, to look through an array of numbers, and attempt to find a particular number (in this case, the block's number)

2. Examining The Program:

Let's examine the C# source code that produces the behavior we see on-screen

• Declaring the instance variables and named constants

  // constant size for the array    private const int BLOCK_ARRAY_SIZE = 10;    // an array of Circles to represent the SoccerBalls    private XNACS1Rectangle[] m_Blocks;    private XNACS1Circle m_SoccerBall; // this is under user control    private int[] m_NumbersToSearchThrough;

  • For this tutorial, we've declared a named constant, BLOCK_ARRAY_SIZE, to set the size of the array of blocks to be 10.  When then declare the array of blocks (m_Blocks), which we'll initialize shortly.  We also declare the array of numbers that we want to search through, with the line
       private int[] m_NumbersToSearchThrough;
    • Note that the length of this array will be different from the length of the block array.
    • Notice also the very long name for the array.  It has the advantage of being very descriptive, and has the disadvantages of being both harder to type, and being a name so long that using it in statements tends to produce very long (and less readable) lines of code.  Consider what other names could have been used, that are equally expressive, but less verbose (m_NumsToSearchThrough? m_NumsToSearch? m_SearchNums? m_Nums?)
• InitializeWorld():
  • We initialize the m_Blocks array using the exact same technique that we used in the previous tutorial.
  • We initialize the m_NumbersToSearchThrough array by creating the array
        m_NumbersToSearchThrough = new int[4];

    and then setting the value of each element by hand:
        m_NumbersToSearchThrough[0] = 2;

        m_NumbersToSearchThrough[1] = 3;

        m_NumbersToSearchThrough[2] = 7;

        m_NumbersToSearchThrough[3] = 9;

    This is a reasonable approach, since we've picked the numbers to search for out of thin air, and there's no obvious pattern here (i.e., we can't easily replace this with a loop).

    • Another option would be to use the array initializer syntax, which is a special way of both creating and initializing arrays, in a single step.  For example, the above lines of code are equivalent to:
          m_NumbersToSearchThrough = new int[] {2, 3, 7, 9};
• UpdateWorld():

  protected override void UpdateWorld() {    if (GamePad.ButtonBackClicked())       this.Exit();    m_SoccerBall.CenterX += GamePad.ThumbSticks.Right.X;    m_SoccerBall.CenterY += GamePad.ThumbSticks.Right.Y;    DisplayNumbersToSearchAtTop();    String foundString = "No Number To Search For!";    // now try to find the colliding block    bool found = false;    int i = 0;    while ((!found) && (i < m_Blocks.Length))    {       if (m_Blocks[i].Collided(m_SoccerBall))       {          // found!          found = true;       }       else          i = i + 1;    }    if (found)    {       int numberToFind = i;       foundString = numberToFind + " was not found in the array";       // This is the classic linear search:       for (int j = 0; j < m_NumbersToSearchThrough.Length; j++)       {          if (m_NumbersToSearchThrough[j] == numberToFind)          {             foundString = "Found the value " + numberToFind + " in the array!";          }       }    }    EchoToBottomStatus(foundString); }

  • UpdateWorld starts by handling the now-standard Back button and right thumbstick, and then goes on to call the DisplayNumbersToSearchAtTop method, which uses the same pattern you've seen in previous tutorials to build up a string (containing all the numbers in the m_NumbersToSearchThrough array), and then display that message at the top of the screen.
  • The rest of the function can (basically) be divided up into two major steps: figuring out which block the soccer ball is overlapping (if any), and if it is overlapping a block, figure out if that block's number is present in the m_NumbersToSearchThrough array.
    • There are three possible outcomes here: 
      1. The soccer ball is not overlapping any blocks, in which case we'll display the message "No Number To Search For!".  We set this message to be the default, using the statement:

            String foundString = "No Number To Search For!";

      2. The soccer ball is overlapping a block, but that block's number is not present in the array, in which case we'll display the message "X was not found in the array" (where X is the block's number).  If the soccer ball is overlapping a block, then we change foundString  to this new message - if the soccer ball doesn't overlap anything, then we'll keep (and display) this message.
      3. The soccer ball is overlapping a block, AND that block's number IS present in the array, in which case we'll display the message "Found the value X in the array!" (where X is the block's number).
  • We use the first loop (and the initialization code before it) to do a linear search on the array of blocks.
       // now try to find the colliding block

       bool found = false;

       int i = 0;

       while ((!found) && (i < m_Blocks.Length))

       {

          if (m_Blocks[i].Collided(m_SoccerBall))

          {

             // found!

             found = true;

          }

          else

             i = i + 1;

       }

    •  The goal for this loop is to either determine that the soccer ball does not overlap any of the rectangles (in which case, it will set the variable found to be false), or else determine that the soccer ball is overlapping a rectangle (in which case, it will set the variable found to be true, and the variable i will hold the index of the rectangle that overlaps the soccer ball.
    • We start by setting i to be zero (which is the index of the first element of the array), and the variable found to false.  We'll use i to keep track of the index of the current element that we're checking, and found to indicate when we should stop the loop.
    • The check for the while loop:
         while ((!found) && (i < m_Blocks.Length))
      says that while we haven't found a rectangle that's overlapping the soccer ball (!found), and (&&) we haven't yet examined all the elements in the array (i < m_Blocks.Length), then check the next element
    • Inside the body of the loop, we have an if/else statement. 
          if (m_Blocks[i].Collided(m_SoccerBall))
      It asks if the block that we're currently examining is overlapping the soccer ball. 
      • If that's true, then we execute the statement
            found = true;
        which will cause the loop to exit, the next time that the program cycles back to the "check" part of the while loop (once found is true, then !found means !true, which translates to false, which causes the loop to stop repeating)
        • It is critical to note that because we will NOT execute the i = i + 1 line this way, when we leave the loop because we've found an overlapping rectangle, the i will store the index of the overlapping rectangle.
      • If the ball isn't overlapping , then we execute the line
                 i = i + 1;
        which will increment the index, so that the next time through the loop we will examine the next element in the array.
      • Notice that while the curly braces aren't required for either the if, or the else, we can legally add the curly braces to just one or the other (in this case, the if part has curly braces, but the else doesn't)
  • If the soccer ball is overlapping a rectangle, then we want to figure out if that rectangle's number is in our array of numbers to search.  But if the soccer ball isn't overlapping any rectangles, then we want to skip to the end of the function, and display the contents of foundString (which will still be "No Number To Search For!", since we haven't changed it) to at the bottom of the screen.  We do this using the statement
       if (found)
    This ensures that we only try to locate the block's number in the m_NumbersToSearchThrough array if we actually found an overlapping block
  • The body of the if statement starts off by creating a couple variables:
          int numberToFind = i;

          foundString = numberToFind + " was not found in the array";

    • First, we create and initialize numberToFind.  This variable isn't necessary, but it does provide a clearer, easier to understand name.  Essentially, we know that since the blocks are numbered 0, 1, 2....9, and that since these numbers correspond with the blocks' indices in the array, therefore the index of the block is the same as it's number.  Since we're looking for the block's number, then the number to find is the same as the block's index. 
    • Next, we set up foundString with a message telling the user that the block's number isn't in the array.  If we do find the number in the array, then we'll replace this message with the "Found it!" message, but if we don't, then we're all set up to display this message.

  • The next thing we do is a very 'classic' linear search, in the sense that finding a value (in this case, a number) in an array is something that many programs do very frequently.  The loop iterates through all the elements in the array:

          // This is the classic linear search:

          for (int j = 0; j < m_NumbersToSearchThrough.Length; j++)

  • And the if statement simply asks "have we found the number we're looking for, here in this element of the array?"

             if (m_NumbersToSearchThrough[j] == numberToFind)

  • If that's true, then we update the message to indicate that we've found the block's number amongst those values stored in the number array:
                foundString = "Found the value " + numberToFind + " in the array!";
    • You'll notice that we don't stop the loop when we find the number.  Since numberToFind has exactly one value, and since the m_NumbersToSearchThrough array contains no duplicates, we know that the if statement can only be true once.  This means that even if soccer ball is over the block whose number is stored in the very first element of the m_NumbersToSearchThrough array, we will still search through the entire array!!
      • In this case, it probably doesn't make a difference, since there's only 4 elements in the array.  But think about what would happen if there were 4,000, or 500,000 or even 6,000,000 elements of the array.
      • One way to tell C# that we want to end the loop early is by keeping a variable (like found), like we did in the prior loop.  Another approach is to use the C# for keyword, like so:
              // This is the classic linear search:

              for (int j = 0; j < m_NumbersToSearchThrough.Length; j++)

              {

                 if (m_NumbersToSearchThrough[j] == numberToFind)

                 {

                    foundString = "Found the value " + numberToFind + " in the array!";

                    break;

                 }

              }

        This tells C# to break out of the nearest enclosing loop (in this case, the for loop)

  • Once all that is done, the EchoToBottomStatus command prints out the appropriate message on the screen.

FURTHER EXERCISES:

1. Start from a blank starter project (1000.201, if you need it), and re-do the code from memory as much as possible.  On your first try, do what you can, and keep the above code open so that when you get stuck, you can quickly look up what you forgot (and that after you finish a line, so that you can compare your line to the 'correct' line).  On the next try, do the same thing, but try to use the finished code less.  Repeat this until you can type everything, without refering the tutorial's code.
   • Repeat this exercise daily for several days, so that you really get the hang of this.  As you go on, periodically review this by re-doing this exercise.
2. Examining The Program
   For this exercise, you should use the same project that was explained in the above tutorial.
   What happens if the soccer ball simultaneously overlaps multiple rectangles?  For example, what happens if the soccer ball overlaps both rectangle #5, and #6?  Why?
3. Listing All Matches
   For this exercise, you should use the same project that was explained in the above tutorial.
   Modify the program so that instead of displaying the contents of the m_NumbersToSearchThrough array along the top, you instead display all the rectangles that the soccer ball overlaps.  If the soccer ball is overlapping no rectangles, then display a message like "No overlapping rectangles".  If the soccer ball only overlaps rectangle #5, then display something like "Overlap with #5", and if the soccer ball overlaps #5 and #6, display something like "Overlap with #5, #6".
   • While it is impossible for the soccer ball to overlap more than 2 squares, you should still write your code so that the program displays a list of all overlapping rectangles - if the soccer ball was large enough to overlap all of the rectangles, then your code should display a list of all the rectangles

	This work is supported in part by a grant from Microsoft Research under the Computer Gaming Curriculum in Computer Science RFP, Award Number 15871 and 16531.
2/8/2010