My question accepts a (listof plane) structure where a plane is a list [airplane_code, date, price]:
- airplane_code is the plane name
- date is 1-365 inclusive where all dates might not be unique for each plane
- price is int[>=0] where all prices are unique for each plane
The function also produces a (listof plane). I need to filter this list according to the two other variable my function accepts (start_date and end_date) first and then by price (in ascending order). However I am restricted to using the binary search concept to sort for price:
def binary_search(lst, target):
beginning = ...
end = ...
while ...:
middle = ...
if lst[middle] < target:
...
##update beginning and end
else:
...
##update beginning and end
I cannot figure out how binary search would allow me to sort a list and would appreciate any help. This is what I have done until now (filtering for date variables given):
def determine(planes, start_date, end_date):
correct_planes = []
plane_price = []
final_selection = []
for plane in planes:
if plane[1] >= start_date and plane[1] <= end_date:
correct_planes.append(plane)
plane_price.append(plane[2])
An example of how the function works:
plane_list = [['A11', 215, 300], ['A22', 260, 750], ['A33', 230, 600], ['A44', 300, 400]]
determine(plane_list, 200, 260) => [['A11', 215, 300], ['A33', 260, 600], ['A22', 260, 750]]
plane
should probably be a tuple, not a list. Tuples are used to store structures, where the position of each field in the tuple denotes its meaning. (e.g. plane[0] is always a str plane name.) Lists are used to store ordered collections of interchangeable items (for example a list ofplane
tuples.) – Jonathan Hartley Jun 4 '16 at 4:11