Finding the Min for positive and negative in python 3.3 list

[Wolfgang Maier]

Chris Angelico <rosuav <at> gmail.com> writes:

>
> > Sort cannot be O(log(n)) and it cannot be faster than a standard O(n)
> > minimum finding algorithm. No valid sorting algorithm can have even a
> > best case performance that is better than O(n). This is because it
> > takes O(n) just to verify that a list is sorted.
> 
> Or looking at it another way: Sorting a list will require, at a bare
> minimum, comparing every element against at least one other element -
> if you could reduce it below that, there would be some element whose
> position you cannot know. Finding the minimum requires precisely that
> number of comparisons: each item against the one current minimum. :)
> 
> ChrisA
> 

Shame on me! You really shouldn't post things, while working on something else
that needs all your attention. You're absolutely right with what you're saying.
I was so fixed on speeding things up with the use of bisect that I wasn't really
thinking carefully about the sorting, and I was delighted when I saw that my
solution was speeding up the range() input example.
Unfortunately, it's only speedy for this example because the input is actually
sorted from the start (so sorted just checks the list -> O(n)). When you use it
on shuffled input, performance is really poor as opposed to the simple min()
solution, so as pointed out by you the costs of sorting are higher than the gain
from using bisect.
What started this whole mess was my gut feeling that you should somehow be able
to exploit all the information you have, and that is that the second minimum
you're looking for cannot be negative, so is at least 0 (or 1 depending on how
you decide to treat 0). So I thought that under this restriction there should be
a faster way to find the minimum than with min(). It only fooled me into
thinking that bisect could be used for it though. Is it really impossible to
beat the min() solution then?

Thanks for your feedback,
Wolfgang