Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
Given a list of some length, containing random numbers.
What method would need the least amount of checks to find the largest & smallest number in the list?
My best guess is: (list_length)/2 amount of checks.
If you compare the first & last item, then 2'nd- first & -last item, and so on, since it makes you check 2 numbers at a time in the list, then update 2 variables with the index of the biggest & smallest number.
Is there a better/faster/more efficient method?
Let's talk about finding the minimum (or maximum only).
If $n$ is the size of the list (not sorted), you will have $n-1$ comparison and $n$ access to the list (if you store the value).
This is due to the fact that numbers are not sorted. So you have to compare all numbers in the given list.
The first with the last, then the minimum of them with the 2nd, the minimum of them etc.
You have to compare the local minimum with all unchecked values otherwise you will miss the results.
Now, you can reduce this number by bounding the list. If you know in advance what is the minimum and/or the maximum (for instance all naturals numbers). You know in advance that if you find a 0, it will be automatically the minimum number in the list. No need to continue checking.
So, in the unsorted list, there is no more efficient way to compare all numbers with the latest minimum found. Or you will make presumption and you will probably get it wrong.
Also, check this good article on finding the minimum and maximum of an array.
If you want the exact minimum/maximum, the most efficient algorithm is storing their estimates and looping over the array comparing their values to each value in the array and updating their values whenever you find some value smaller/larger. You cannot look at fewer elements without additional assumptions because imagine you deterministically choose a subset of the array to look at. An adversary could see what portions of the array you’ll look at and then place the minimum/maximum outside of those array portions. The only way for you as an algorithm maker to beat the adversary is to see the whole array before deciding you’ve found a minimum/maximum.
If you were okay with allowing error, you could always try to estimate the minimum/maximum by choosing a much smaller random subset of elements, say of size $\sqrt{n}$, and then looping over this smaller set and computing the minimum/maximum of this and using that as an estimate. Of course, you’d have a decent probability of being wrong, but perhaps it would end up being okay for your application. There’s also more complicated streaming algorithms you might investigate to find approximation techniques.
