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
Watch this YouTube video , answer the following questions:
To use binary search to look for a value in the array above, what needs to be done first? Write code to achieve that.
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?
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?
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