2. One of the key things to know about a binary search is that you cannot:
3. How would you go about performing a binary search on the following list?
4. If you had the following list, what would the formula for finding the mid point be?
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))
It stores the sum of all the elements in the list - in this case 19.
None of the above apply
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
7. If the item being searched for is not found in the mid point, what happens next?
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))
Line 3: last = len(item_list)-1 …this checks to see if the item is last and therefore can be discarded
None of the above apply
Line 10 if item < item_list[mid]: …this checks if the item is located before or after the mid point
first = 0 - this checks to see if the item being searched for is now first (e.g found)
9. Here is the pseudocode for another binary search. Fill in the blanks
10. A binary search is generally excellent for…..