XNA Game-Themed CS1 Examples (XGC1)

Release 2.0 (XNA V3.1)
2/8/2010

Topic: Topic.6.Arrays
Example: Ex_5.LinearSearch

Arrays: Linear Search Through An Array (For Loop)



References:

Goals:



1. Obtain the example code

Download and unzip the zip file and you will see an ExampleProgram folder. Open the ExampleProgram folder, the EXE folder contains the compiled program and you can double click on the .sln file to work with the source code.

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


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.
  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".

Project home page: The Game-Themed Introductory Programming Project.
Kelvin Sung
Computing and Software Systems
University of Washington, Bothell
ksung@u.washington.edu
Michael Panitz
Business And Information Technology
Cascadia Community College
mpanitz@cascadia.eduu

Microsoft Logo 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