Preview

20 - Searching

 1. One of the strengths of computers is their ability to find things quickly. This ability is called ________.

  sorting

  mixing

  lending

  searching

 2. Sequential or Linear search typically starts at the first element in an array or ArrayList and looks through all the items one by one.

  TRUE

  FALSE

 3. Binary search can only be used on data that has been _____________________.

  duplicated for security purposes

  stored in index numbers that do not exceed 100

  stored in a random order

  sorted or stored in order

 4. A Linear search can also operate only on data that is in order.

  TRUE

  FALSE

 5. A Binary Search checks the ______________________is less than, equal, or greater than the desired value and then based on the results of that it narrows the search.

  middle of the data to see if that middle value

  first value of the data to see if that first value

  last value of the data to see if that last value

  second last value of the data to see if that second last (length-1) value

 6. Sequential search is also called a _____________search.

  linear

  binear

  sorting

  binary

 7. Sequential search is the only method that can be used to find a value in _________________.

  a linear binary tree

  a sorted list

  a sorted sublist

  an unsorted list

 8. Which of the following statements is correct, regarding the following code?
public class ListSearcher
{

   /** Finds the index of a value in an array of integers.
     * @param elements an array containing the items to be searched.
     * @param target the item to be found in elements.
     * @return an index of target in elements if found; -1 otherwise.
     */
   public static int xSearch(int[] elements, int target)
   {
     for (int j = 0; j < elements.length; j++)
     {
       if (elements[j] == target)
       {
         return j;
       }
     }
     return -1;
   }

   public static void main(String[] args)
   {
     int[] numArray = {3, -2, 9, 38, -23};
     System.out.println("Tests of sequentialSearch");
     System.out.println(xSearch(numArray,3));
     System.out.println(xSearch(numArray,9));
     System.out.println(xSearch(numArray,-23));
     System.out.println(xSearch(numArray,99));
   }

}

  It is the code for either a linear or binary search

  It is the code for a linear search

  It is the code for a binary search

  it is the code for a linear sort (not a search)

 9. Which of the following statements is correct, regarding the following code?
import java.util.*;

public class ArrayListSearcher
{

  /** Finds the index of a value in an ArrayList of integers.
    * @param elements an array containing the items to be searched.
    * @param target the item to be found in elements.
    * @return an index of target in elements if found; -1 otherwise.
    */
  public static int sequentialSearch(ArrayList elements, int target)
  {
    for (int j = 0; j < elements.size(); j++)
    {
      if (elements.get(j) == target)
      {
        return j;
      }
    }
    return -1;
  }

  public static void main(String[] args)
  {
    ArrayList numList = new ArrayList();
    numList.add(3);
    numList.add(-2);
    numList.add(9);
    numList.add(38);
    numList.add(-23);
    System.out.println("Tests of sequentialSearch");
    System.out.println(sequentialSearch(numList,3));
    System.out.println(sequentialSearch(numList,9));
    System.out.println(sequentialSearch(numList,-23));
    System.out.println(sequentialSearch(numList,99));
  }

}

  All of the options here are correct, with regard to the code

  The code is demonstrating a linear search.

  The code here shows the use of an ArrayList as opposed to an array

  .size() and get(i) is used with ArrayLists instead of length and [i] which are used in arrays.

 10. Which will cause the longest execution of a sequential search looking for a value in an array of integers?

  The value isn't in the array

  The value is in the middle of the array

  The value is the first one in the array

   The value is the last one in the array

 11. Which will cause the shortest execution of a sequential search looking for a value in an array of integers?

  The value is the first one in the array

  The value is in the middle of the array

  The value isn't in the array

  The value is the last one in the array

 12. It is also possible to look for a string in an array or list. But, when you look for a string be sure to use == rather than equals.
Remember that == is only true when the two references refer to the same object, 
while equals returns true if the characters in the two objects are the same.

  FALSE

  TRUE

 13. Binary search calculates the_______________ where left starts out at 0 and right starts out at the array length - 1 (the index of the last element).

  left index as left + middle / right

  middle index as left + right / 2

  None of these options are correct

  right index as left + right / middle

 14. Consider the following code for a binary search and the different tests at the bottom of the code. What is test 2 likely to be for?
public class SearchTest
{
   public static int binarySearch(int[] elements, int target) {
      int left = 0;
      int right = elements.length - 1;
      while (left <= right)
      {
         int middle = (left + right) / 2;
         if (target < elements[middle])
         {
            right = middle - 1;
         }
         else if (target > elements[middle])
         {
            left = middle + 1;
         }
         else {
            return middle;
         }
       }
       return -1;
   }

   public static void main(String[] args)
   {
      int[] arr1 = {-20, 3, 15, 81, 432};

      // test1 when the target is in the middle
      int index = binarySearch(arr1,15);
      System.out.println(index);

      // test2 ____________________________________
      index = binarySearch(arr1,-20);
      System.out.println(index);

      // test3 when the target is in the array - last
      index = binarySearch(arr1,432);
      System.out.println(index);

      // test4 when the target is not in the array
      index = binarySearch(arr1,53);
      System.out.println(index);
   }
}

  when the target is the first index number

  when the target is the whole array

  when the target is the first item in the array

  when the target is the last -1 item in the array

 15. Binary search is much slower than linear search, especially on large data sets, but it can only be used on sorted data.

  FALSE

  TRUE

 16. Often with runtimes, computer scientist think about the ________ behavior. With searching, the ___________ is usually if you cannot find the item.

  worst case

  lower case

  instant case

  best case

 17. Which will cause the shortest execution of a binary search looking for a value in an array of integers?

  The value is the last one in the array

  The value isn't in the array

  The value is in the middle of the array

  The value is the first one in the array

 18. Which of the following conditions must be true in order to search for a value using binary search?
I. The values in the array must be integers.
II. The values in the array must be in sorted order.
III. The array must not contain duplicate values.

  I and II

  I only

   II only

  II and III

 19. How many times would the loop in the binary search run for an array int[] arr = {2, 10, 23, 31, 55, 86} with binarySearch(arr,55)?

  2

  1

  4

  3

 20. If you had an ordered array of size 500, what is the maximum number of iterations required to find an element with binary search?

  approximately 9 times

  approximately 15 times

  500 times

  2 times