Lowest complexity - Number closest to 0 I'm currently trying to improve my algorithm skills and I was trying a simple algorithm :
Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his opposite, we want to return the positive one.
My current complexity on this algorithm is O(n). Is it possible to get a lower one ?
My current solution looks at all the values. I was thinking about a binary search, but we're not looking for a specific number, and the list of integers is not sorted.
Thanks for the help !
If you want an algorithm that is always correct you can not do better, precisely because you have to look at all the values at least once (except if you find a $0$ somewhere, then you can immediately return that).
Otherwise, suppose your run your algorithm $A$ some input $I=[a_1,a_2,\ldots,a_n]$, and it returns a value $v\neq 0$ without looking at all numbers in $I$. Say it didn't look at $a_k$. Then we could just as well set $a_k=0$ and $A$ wouldn't know about it (because it didn't look at $a_k$). Thus $A$ will be wrong on this (modified) input.
That is of course assuming that setting $a_k = 0$ doesn't contradict some assumption you have about the data (for example it being sorted).