1
$\begingroup$

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 !

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ That's what I was thinking. Thanks for the answer ! $\endgroup$ – Papy Poule Sep 15 '20 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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