current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote -1 down vote favorite

A list is strictly convex if its elements first decrease then increase. How can I write a function in python that accepts a convex list and returns its minima in time complexity O(log(n)), n being the size of the list. (NO USE OF ANY BUILT IN FUNCTIONS OVER LISTS)

share|improve this question

closed as unclear what you're asking by MichaelT, Wayne M, Giorgio, GlenH7, Bart van Ingen Schenau Jun 15 at 10:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.
    
what did you try, BTW if the elements first increase and then decrease the minimum will be either the first or the last element –  ratchet freak Jun 14 at 12:40
1  
Why can't you use any of the built in list functions? If this is homework, please also read Open letter to students with homework problems –  MichaelT Jun 14 at 13:31
    
This question appears to be off-topic because it appears to be about homework. –  Giorgio Jun 14 at 15:01
    
@Giorgio - some homework questions can be on-topic. In this case, the OP has not demonstrated an understanding of the problem and they haven't presented a specific issue they are trying to work through while solving their homework problem. Definitely needs to be closed. –  GlenH7 Jun 15 at 2:43
add comment

2 Answers 2

up vote 0 down vote accepted

Don't speak Python, but the idea seems fairly simple:

  • you pick the element in the middle and its left (or right) neighbour, A and B
  • you compare those elements A and B against each other
    • if B < B, choose A as new E, and start over
    • if A >= B, choose B as new S, and start over
  • at some point you are left with only 1 element, which is the minimum

Remarks:

  • The assumption here is, that no two elements directly following each other are equal, except maybe at the minimum. The term "strictly convex" seems to imply that. However, if you can't guarantee that, it may need some extra tweaking.
  • You will need some special-case handling at the beginning/end of the list, or if the list is empty, etc.
  • can be implemented recursively
share|improve this answer
    
Great. Thanks a lot. –  user3740259 Jun 14 at 13:47
add comment
up vote 0 down vote

Since either the first or last element would have to be the lowest, how about this? I even provide a key argument

def min_convex(a_list, key=None):
    if key:
        first, last = key(a_list[0]), key(a_list[-1])
    else:
        first, last = a_list[0], a_list[-1]
    if first < last:
        return first
    else:
        return last

EDIT: well now you've changed your question.

Since the built-in min is not a LIST FUNCTION (it's a built-in function, not a list method), then how about 

min(a_list)
share|improve this answer
    
I'm sorry. It's first decrease then increase. Question edited. –  user3740259 Jun 14 at 12:46
    
I'm sory. I am a bit troubled as I have been trying to figure out the solution for quite a time but have been unable to. –  user3740259 Jun 14 at 13:31
    
@user3740259 could you add what you've tried doing so far to the question? Where have you gotten stuck? Searching for "binary search python" in google brings up stackoverflow.com/questions/212358 as a top hit. Have you looked at that? Do you understand how to implement a binary search on a regular sorted list? –  MichaelT Jun 14 at 13:42
    
@AaronHall min(a_list) operates in O(n) time. If the list is sorted you can do much better than that. –  MichaelT Jun 14 at 13:43
    
@MichaelT I didn't want the whole code. I just wanted the logic needed to solve the problem. The answer by JensG is what I was looking for. Thanks, anyway. –  user3740259 Jun 14 at 13:46
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.