logotransparent.png

Legion of Learners

www.lol-101.com

  • Home

  • Classrooms

  • Courses

  • About Us

    • Executive Team
    • Board Members
  • Resources

  • More

    Use tab to navigate through the menu items.
    To see this working, head to your live site.
    • Categories
    • All Posts
    • My Posts
    sfolax6776
    Oct 29, 2021
      ·  Edited: Nov 04, 2021

    3-3 Linear and Binary Search

    in AP Computer Science A

    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

    2 comments
    0
    joycexinxu
    Nov 11, 2021

    https://replit.com/@JoyceXu1/SortingCandy#Main.java

    0
    William Li
    Nov 12, 2021

    https://replit.com/@offexe/sorting

    0
    2 comments

    Questions? Email us at legionoflearners@gmail.com or join our WeChat group!

    • lol-101dotcom

    ©2020 Legion of Learners