Compare the linear search (see LinearSearcher.java in section 14.6.1 of the text

Question

Compare the linear search (see LinearSearcher.java in section 14.6.1 of the textbook on page W646) and binary search (see BinarySearcher.java in section 14.6.2 of the textbook on page W648, or download the zip file on the Week 7 page called ser200_chapter14_samples.zip) algorithms by tracing a search for the numbers 8, 33, 84 in the array {4, 8, 12, 23, 54, 84, 89, 110}. For both algorithms, list (in order) the elements of the array that the algorithm will check against before finding the correct result. If an element cannot be found, note which number the algorithm will stop on.

/**
   A class for executing linear searches in an array.
*/
public class LinearSearcher
{
   /**
      Finds a value in an array, using the linear search
      algorithm.
      @param a the array to search
      @param value the value to find
      @return the index at which the value occurs, or -1
      if it does not occur in the array
   */
   public static int search(int[] a, int value)
   {
      for (int i = 0; i < a.length; i++)
      {
         if (a[i] == value) { return i; }
      }
      return -1;
   }
}

/**
   A class for executing binary searches in an array.
*/
public class BinarySearcher
{
   /**
      Finds a value in a range of a sorted array, using the binary
      search algorithm.
      @param a the array in which to search
      @param low the low index of the range
      @param high the high index of the range
      @param value the value to find
      @return the index at which the value occurs, or -1
      if it does not occur in the array
   */
   public static int search(int[] a, int low, int high, int value)
   {
      if (low <= high)
      {
         int mid = (low + high) / 2;

         if (a[mid] == value)
         {
            return mid;
         }
         else if (a[mid] < value )
         {
            return search(a, mid + 1, high, value);
         }
         else
         {
            return search(a, low, mid - 1, value);
         }       
      }
      else
      {
         return -1;
      }
   }
}

Explanation / Answer

array = 4 8 12 23 54 84 89 110

Linear search:

8

compare 4, compare 8, return

33,

compare 4, 8, 12, 23, 54, 84, 89, 110 ,didn't found return

84

compare 4, 8, 12, 23, 54, 84, found return

Binary search:

8

Mid = 23, 23 greater than 8, check in 4, 8, 12

Mid = 8, 8 is same, return

33

check with 23, 23 is smaller, check in 54, 84, 89, 110

check 89, 89 is greater check in 54,

not same, return not found

84,

check with 23, 23 is smaller, check in 54, 84, 89, 110

check 89, 89 is greater check in 54, 84

check with 54, 54 is less, check in 84

equals, return

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.