Are we aiming for a solution that makes less than 2(n-1) comparisons in the average case? Or less than that even in the worst case?
Also, should the solution be a general one that doesn’t depend on the contents of the collection being integer? Or can it be specific to integers?
Thanks!
We don’t limit the way you solve the problem, in interview the interviewer mostly won’t tell you what they are looking for exactly in terms of time and space complexities in the beginning.
About worst case, you shall think about what your algorithm is since no way to define worst case without an algorithm.
It does not have to be integers as long as there is a total order of those elements (from Math perspective).
The reason I ask about worst case is that I have a solution in mind. But the number of comparisons it performs varies (depending on the actual collection entries) from n-1 to 2(n-1). I’m guessing this isn’t good enough. Is that correct?
Feel free to compare your solution with the one in the book as that one is the optimal one.
I don’t want to look at the solution in the book. I feel that would be taking the easy way out. 
So far I’ve only looked at the solution 3 times. And that was only after I was 100% sure that I didn’t have any idea about how to solve those problems.
I haven’t looked at the hint either. I wanted to delay that as long as possible, in case it makes the solution too obvious. I’ll keep trying… I’m not ready to give up yet!!!
One approach would be to check if each entry is less than the minimum entry so far. If so, we improve the minimum entry. That’s one comparison and we move to the next entry. If not we do a second comparison with the maximum entry so far. This makes a maximum of 2(n-1) comparisons for the entire collection, when the entries are in increasing order. But (n-1) comparisons when they’re in decreasing order. So somewhere between (n-1) and 2(n-1) comparisons for any other ordering of entries.
Is it possible to do better than this? I only want to know - yes or no.
Regarding the variant, where it asked what is the least number of comparisons required to find the min/max in the worst case, would that be (3/2) * (n-3) + 3 for odd length arrays, and (3/2) * (n-2) + 1 comparisons for even length arrays?