0

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]]

4
  • I don't understand your constraints to use binary search... You seems to know how to compare plane, so any sort by comparison should work. You probably should have a look at wiki.python.org/moin/HowTo/Sorting Commented Jul 16, 2013 at 7:31
  • The course I am taking wants us to get more experience with binary search (but have taught us very less of it). Therefore I am restricted to binary search. Commented Jul 16, 2013 at 7:35
  • Binary search is not a sorting algorithm. It is a way to search for an item in a collection that has already been sorted. Commented Jun 4, 2016 at 4:09
  • FWIW, 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 of plane tuples.) Commented Jun 4, 2016 at 4:11

2 Answers 2

0

A complex sorting function would be much simpler, but you can use binary sort also. This can best be achieved using lambdas.

Refer to these links for implementation details:

1) Complex sort with multiple parameters?

2) Advanced sorting criteria for a list of nested tuples

EDIT: According to hivert's comment, you can sort using itemgetter too. The implementation details are here: http://wiki.python.org/moin/HowTo/Sorting/#Sort_Stability_and_Complex_Sorts

Choose whatever method is more comfortable for you.

Sign up to request clarification or add additional context in comments.

3 Comments

As I mentioned above, the course I am taking wants us to get more experience with binary search and so I am restricted to binary search. I will definitely explore this method as well.
Sorry, didn't see the comment.
I thought I can only use binary search meant that you only know how to use binary search.
0

This can be cleanly done using python sorting algorithm. Your constraints of doing binary search only, do not seem good from coding as well as performance reasons, since the list is not going to be very big.

>>> plane_list = [['A11', 215, 300], ['A22', 260, 750], ['A33', 230, 600], ['A44', 300, 400]]
>>> start_date,end_date = 200, 260
>>> new_list = [x for x in plane_list if start_date <= x[1] <= end_date]
>>> new_list
[['A11', 215, 300], ['A22', 260, 750], ['A33', 230, 600]]
>>> new_list = sorted(new_list,key= lambda x:x[1])
>>> new_list
[['A11', 215, 300], ['A33', 230, 600], ['A22', 260, 750]]

1 Comment

As I mentioned above, the course I am taking wants us to get more experience with binary search and so I am restricted to binary search. Thank you for an answer though.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.