Preview

02 - Binary Search

 1. A binary search is …

  an algorithm that uses binary sequences to analyse and search for data

  an algorithm that works in binary (1s and 0s) e.g. can only search for a 0 or 1

  an algorithm that is undoubtedly and undeniably the best searching technique

  an algorithm that takes the data and keeps dividing it in half until it finds the item it is looking for.

 2. One of the key things to know about a binary search is that you cannot:

  use this technique on an unsorted list

  use this technique on numbers

  use this technique on non-binary data

  use this technique on a sorted list

 3. How would you go about performing a binary search on the following list?
Andy, Clarke, Bob, Xavier, Fred, Jonathan

  You'd start by finding the mid point

  Well, you'd start by realising this is not a sorted list, so a binary search cannot be implemented

  You'd start by counting the elements in the list and doubling them

  You'd start by putting 'Andy' at the end of the list

 4. If you had the following list, what would the formula for finding the mid point be?
List = Andy, Bob, Ed, Gina, Jonathan

#First add the index numbers to each element in the list

0          1         2          3             4       
=========================================================
Andy       Bob       Ed        Gina        Jonathan

#Second, find the mid point by using the formula:

..........................................................................................

  midpoint = length_of_list/4

  midpoint = high + low / high (where low = 0 and high = 1)

  midpoint = low+high//2 (where low = 0 and high = 4)

  midpoint = n /3

 5. In the following code for a binary search, what is the variable 'last'?
def binary_search(item_list,item):
 first = 0
 last = len(item_list)-1
 found = False
 while( first<=last and not found):
  mid = (first + last)//2
  if item_list[mid] == item :
   found = True
  else:
   if item < item_list[mid]:
    last = mid - 1
   else:
    first = mid + 1 
 return found
 
print(binary_search([1,2,3,5,8], 6))
print(binary_search([1,2,3,5,8], 5))

  None of the above apply

  It stores the sum of all the elements in the list - in this case 19.

  It stores the length of the list -1, in this case last = 4 (the highest index number)

  It stores the length of the list - in this case 5

 6. After the mid point has been found, what is this line of code doing? if item_list[mid] == item : found=True

  If the mid point is not equal to the item being searched for, exit the program

  If the mid point (e.g. 2) is equal to the number being searched for, keep searching

  If the mid point of the list is infact the item searched for then ….set the found flag to True (item found!)

  None of the above apply

 7. If the item being searched for is not found in the mid point, what happens next?

  All elements except one are discarded and the remaining element is usually what we want

  The algorithm stops and cannot proceed

  One half of the list is discarded

  None of the above apply

 8. Which part of the code checks to see which part of the list to discard?
def binary_search(item_list,item):
 first = 0
 last = len(item_list)-1
 found = False
 while( first<=last and not found):
  mid = (first + last)//2
  if item_list[mid] == item :
   found = True
  else:
   if item < item_list[mid]:
    last = mid - 1
   else:
    first = mid + 1 
 return found
 
print(binary_search([1,2,3,5,8], 6))
print(binary_search([1,2,3,5,8], 5))

  None of the above apply

  first = 0 - this checks to see if the item being searched for is now first (e.g found)

  Line 3: last = len(item_list)-1 …this checks to see if the item is last and therefore can be discarded

  Line 10 if item < item_list[mid]: …this checks if the item is located before or after the mid point

 9. Here is the pseudocode for another binary search. Fill in the blanks
OUTPUT "Which customer do you want to find?"
INPUT user inputs John Smith
STORE the user's input in the customer_name variable
customer_found = False
(we need to create a flag that identifies if the customer is found)

??-------------------------------------------------------------------------------------
 Find midpoint of list
 IF customer_name = record at midpoint of list THEN
  customer_found = True
 ELSE IF customer comes before the midpoint THEN
  throw away the second half of the list
 ELSE 
  throw away the first part of the list
OUTPUT customer details

  WHILE customer_found = False:

  mid point = Found

  IF mid point = customer(1)

  customer_found = customer_found + 1

 10. A binary search is generally excellent for…..

  small, unsorted lists

  very small, sorted lists

  large, sorted lists

  large, unsorted lists