3-3 Linear and Binary Search

A. Notes

Linear search applies to any arrays, sorted or unsorted. This page has an animated gif to show the process.

for each item in the array
      if match item == value 
          return the item's location
      end if
   end for

Binary search applies to sorted arrays only, it takes advantage of the sorting to search much more efficiently. This page has an animated gif to show the process. The pseudocode is here:

Function binary_search
   A ← sorted array
   len ← length of array
   x ← value to be searched

   Set lowerBound = 0; Set upperBound = len-1 
   while x not found
      if upperBound < lowerBound // search is done!
         EXIT: x does not exists.
         // it doesn't matter if upperBound or lowerBound is even or odd, midPoint is always a whole number due to int division in Java. 7 elements will be split into 3 and 4, which does not affect the search result.
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2  
      if A[midPoint] < x
         set lowerBound = midPoint + 1
       if A[midPoint] > x
         set upperBound = midPoint - 1
       if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   end function

B. HW:

Watch this YouTube video , answer the following questions:

{30099,181263,10128,5238,3839,5170,5641,11000,15973,1200,12500,87337,107430,227931,56400}

1. To use binary search to look for a value in the array above, what needs to be done first? Write code to achieve that.

2. Take a random number (for example x=1234), using linear search, how many times do you need to compare to know if x can be found in the array?

3. Take a random number (for example x=1234), using binary search, how many times do you need to compare to know if x can be found in the array?

4. Create a list of candies such as the one below. Use selection sort algorithm to sort it, then ask the user what his/her favorite candy is, and use binary search to search in the list. If the user's favorite candy is not on the list, print "Sorry, we don't have it", otherwise print " Yes, it is number x on our list!"

Necco Wafers
Pop Rocks
Nerds
Jawbreakers
Jolly Ranchers
Smarties
Milk Duds
Charms Blow Pop
Kit Kat
Skittles
Hi-Chew
Sour Patch