Loops, Lists, Conditionals
The idea here is to ask the right questions in order to figure out what is required.
def find_largest_smaller_than(nums, xnumber):
"""Find largest number in sorted list that is smaller than given number."""
# START SOLUTION
# Fail-fast optimization: since our list is sorted, if the first number
# is bigger, a smaller number isn't in our list
if nums[0] >= xnumber:
return None
# Optimization: if the last number isn't too big, it's the answer
if nums[-1] < xnumber:
return len(nums) - 1
# Else, loop through and return the index right before the first number
# that is too big
for i, num in enumerate(nums):
if num >= xnumber:
return i-1
This has O(n) runtime; there are two cases where it can get out of the loop fast, but it still scales with n.
Advanced: Can you find a better runtime for this? There is an O(log n) solution.
Given that our list is sorted, we can search it more quickly than having to scan each item. Instead, we can use the principle of binary search to search it.
We could write the binary search code ourself, but Python has a built-in library, bisect, that does this for us.
def find_largest_smaller_than_bisect(nums, xnumber):
"""Find largest number in sorted list that is smaller than given number.
Advanced version:
Since we have a list, we can search it quickly using binary search.
Python has a nice library, `bisect`, that can do that.
For example:
>>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], 10)
2
>>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], 33)
4
>>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], -1)
1
Never find xnumber --- it's not smaller than itself!
>>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], 8)
1
If no such number exists, return None:
>>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], -10) is None
True
"""
from bisect import bisect_left
# Fail-fast optimization: since our list is sorted, if the first number
# is bigger, a smaller number isn't in our list
if nums[0] > xnumber:
return None
insertion_point = bisect_left(nums, xnumber)
return insertion_point - 1
if nums[insertion_point] == xnumber:
return insertion_point - 1
else:
return insertion_point