What is best efficient algorithm for "Given an unsorted array of positive integers and an integer N, return N if N existed in the array or the first number that is smaller than N." Problem ?

Question

I had this question:

Given an unsorted array of positive integers and an integer N, return N if N existed in the array or the first number that is smaller than N.

in an interview and wanted to know what would be the best efficient algorithm to solve it?

I had given two approaches using hash and sorting array but it was not correct and efficient approach. I would really appreciate if someone can give an optimal algorithm for this problem.

Answer 1

I'm assuming this is in a C-style language; if not, please update the question to reflect the language.

If the array isn't sorted, then you have no choice but a (potentially) full traversal of the array to look for N, as any sorting operation is going take longer than simply traversing the array (other than by finding the element by "blind luck"). Something akin to this would probably be the most efficient (unless I'm missing something)

int retVal = -1;

for(int i = 0; i < ARRAY_LENGTH; i++)
{
    if(array[i] == N) return N;
    if(retVal == -1 && array[i] < N) retVal = array[i];
}

return retVal;

As suggested elsewhere, you can modify

if(retVal == -1 && array[i] < N) retVal = array[i];

to

if(retVal < array[i] && array[i] < N) retVal = array[i];

In order to get the largest value that's smaller than N, rather than simply the first.

Answer 2

Scan through the list from beginning to end, if you see a value less than N, hold on to the first one until you reach the end, or find N. If you find N, return it, if you reach the end, return the value you've held on to. Presumably there'd have to be some value to return if all the values were greater than N, but the problem doesn't state that.

O(N) performance, O(1) space usage.

It's a little trickier if you're looking for the largest value smaller than N. In which case, instead of holding on to the first value smaller than N, you simply grab a new value every time you find a value smaller than N, but larger than the value you are currently holding on to.

Simply replace

if(array[i] < N && retVal == -1) retVal = array[i];

with

if(array[i] < N && retVal < array[i]) retVal = array[i];

in Adam's answer