Searching Arrays

Objective #1: Use a sequential search algorithm with arrays

• A common algorithm used with arrays is the sequential search (aka linear search).
• The sequential search uses a loop to methodically inspect each element of an array until the item which you are looking for is found. Typically a for loop is used rather than a while loop. You simply check each element of an array position by position until you find the one that you are looking for.
• I use a sequential search when I look for a piece of chocolate cake on the dessert line at the Old Country Buffet restaurant! My eyes carefully scan the available pieces of cake from the beginning of the dessert buffet line to the end. When I find the the first piece of chocolate cake, I'm finished!
• In any search, the item upon which the search is based is called the key. For example, if you are searching student records for a student named John Doe then the key might be "Doe".
• An advantage to using the sequential search algorithm is that it is relatively easy to code.
• A flag variable (usually of the boolean data type) can be used to keep track of whether the key was found or not.
• A break statement can be used to exit early from a loop as soon as the key is found.
• Additional variables can be used to keep track of the maximum or minimum value in the array, the number of occurrences of the key, or the position within an array.
• In addition to using a sequential search to look for a number in an array of integers, you could even search through an array of objects looking for a specific object (e.g looking for a password in an array of String objects.)
• Here is an animation of a linear search http://www.cosc.canterbury.ac.nz/mukundan/dsal/LSearch.html
  
  
• The following algorithm searches through an array of integers named numbers for the value 99:
  
  *********************** version with an array *************************
  
  boolean found = false;
  int position = -1;
  
  for (int i = 0; i < numbers.length; i++)
  {
     if (numbers[i] == 99)
     {
        found = true;
        position = i;
        break;
     }
  }
  
  if (found)
  {
     System.out.println("The first occurrence of the key was found in position " + position);
  }
  else
  {
     System.out.println("The key was not found.");
  }
  
  Notice the use of the boolean, flag variable found. A flag variable is used in many situations to keep track if something is on or off or up or down. In this case, found is true if the key is in the array and it is false if it is not found anywhere in the array. Rather than using the boolean data type, you could use an int variable as a flag variable setting it equal to 1 if it was found and 0 if it was not found. However, the code is easier to understand with the boolean.
  
  Also notice that the variable position is used to mark where the key was found within the array. Sometimes it is only necessary to know if a key is found or not. Other times, it is important to determine where exactly the key is found in an array. Be sure to add one to the position if the end user isn't aware that arrays are zero-based. Why do you think position is initialized to -1 rather than 0 in the example above?
  
  Here is a version of the same algorithm using a while loop instead of a for loop:
  
  boolean found = false;
  int i = 0;
  
  while (!found && i < numbers.length)
  {
  
     if (numbers[i] == 99)
     {
        found = true;
     }
     else
     {
        i++;
     }
  
  }
  
  if (found)
  {
     System.out.println("The first occurrence of the key was found in position " + i);
  }
  else
  {
     System.out.println("The key was not found.");
  }
  
  
• Another useful algorithm is one that counts the number of occurrences of a value in array. Here are algorithms that count the number of occurrences of the value 99 in an array:
  
  int count = 0;
  
  for (int i = 0; i < numbers.length; i++)
  {
     if (numbers[i] == 99)
     {
        count++;
     }
  }
  
  System.out.println("The key occurs " + count + " times.");
  
  
  
• Another useful algorithm is one that finds the maximum (or minimum) value in an array. Study the following examples which find the greatest value in an array:
  
  int max = numbers[0];   // or   int max = Integer.MIN_VALUE;
  int position = 0;
  
  for (int i = 1; i < numbers.length; i++)
  {
     if (numbers[i] > max)
     {
        max = numbers[i];
        position = i;
     }
  }
  
  System.out.println("The max value is " + max + " in position " + position);
  
  
  
• Sometimes you may need to remove a certain element from an array.
  
  // remove the zeros from the array
  int[] numbers = {2, 0, 0, 3, 4};
  
  for (int i = 0; i < numbers.length; i++)
  {
     if (numbers[i] == 0)
     {
        // shift existing numbers to the left
        for (int j = i + 1; j < numbers.length; j++)
           numbers[j] = numbers[j + 1];
     }
  }
  
  
• Parallel arrays are two separate arrays that are used together in the logic of an algorithm to store associated data. For example, an array of names and an array of scores where the score in position zero of the scores array belongs to the person whose name is found in position zero of the names array and so on. Two parallel arrays are the same size but they do not have to contain elements of the same data type. The names array would be an array of strings and the scores array would be an array of integers.
  
  For example, you may want to search one parallel array for the greatest gpa and then print the associated name of the student who has the greatest gpa.
  
  String[] names = new String[10];
  double[] gpas = new double[10];
  // pretend that these two parallel arrays are filled with students' names and matching gpa's
  double maxSoFar = gpas[0];
  
  for (int i = 1; i < names.length; i++)
  {
     if (gpas[i] > maxSoFar)
     {
        maxSoFar = gpas[i];
        indexOfMax = i;
     }
  }
  
  System.out.println("The student with the highest gpa is " + names[indexOfMax]);
  
  Notice that maxSoFar was initialized to gpas[0] rather than the value 0. Also, notice that the loop variable i is initialized to 1 rather than 0.
  

Objective #2: Trace and apply the binary search algorithm.

• If the data in an array is already sorted in order (alphabetically for example) then a binary search is much more efficient and quicker than a linear search.
  
  
• In the case of a binary search, you first examine the "middle" element. If that element is "lower" (alphabetically, for example) than the element which you are looking for, then you discard the lower half of the data and continue to search the upper half. The process repeats itself when you then look at the middle element of the remaining "upper half" of the data.
  
  
• Here is an animation of a binary search http://www.cosc.canterbury.ac.nz/mukundan/dsal/BSearch.html & here is a video http://www.youtube.com/watch?v=k-eNRYdkBa8. If this link does not work, you can find many binary search animations using Google or YouTube.
  
  
• The binary search algorithm requires the following preconditions:
  • The data must be sorted.
  • The number of elements in the list must be stored in a separate variable.
  • The programmer must be able to randomly access elements in the list by relative position
    
    
    
• Here's a code segment
  
  while (low <= high && !found)
  {
     mid = (low + high) / 2;
  
     if (key > numbers[mid])
     {
        low = mid + 1;
     }
     else if (key < numbers[mid])
     {
        high = mid - 1;
     }
     else
     {
        found = true;
     }
  
  }
  
  if (found)
  {
     System.out.println("The value" + key + " was found in position " + mid);
  }
  else
  {
     System.out.println("The value" + key + " was not found");
  }