Join the Stack Overflow Community
Stack Overflow is a community of 6.7 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up

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

share|improve this question
    
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 – hivert Jul 16 '13 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. – user2541757 Jul 16 '13 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. – Jonathan Hartley Jun 4 '16 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.) – Jonathan Hartley Jun 4 '16 at 4:11

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.

share|improve this answer
    
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. – user2541757 Jul 16 '13 at 7:40
    
Sorry, didn't see the comment. – Xaranke Jul 16 '13 at 7:41
    
I thought I can only use binary search meant that you only know how to use binary search. – Xaranke Jul 16 '13 at 7:42
    
I guess my wording was wrong. Sorry about that. – user2541757 Jul 16 '13 at 7:45

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]]
share|improve this answer
    
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. – user2541757 Jul 16 '13 at 7:38
    
@saurs My apologies, I did not read the comment. – DhruvPathak Jul 16 '13 at 7:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.