Efficient algorithm for: Given an unsorted array of positive integers and an integer N, return N if N existed in array or the first number <N

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.