Finding the index of a given value in a pre-sorted array

Question

Today, I went for an interview and the interviewer asked me how I would find the index of a given value (number) in a pre-sorted array like this:

$preSortedArr=array(23,32,36,41,45,54);

He also said that using recursion is not allowed.

I think the function should look like this:

function findIndexByValue($preSortedArray,$value){            
//some codes here       
}

What solution do you think he was expecting from me?

EDIT: Sorry, I forgot to add that he originally asked me to write pseudocode, but I said I didn't know. Then I tried to write it in PHP, but I think he's expecting a language-independent solution.

Answer 1

$key = array_search("23", $array);

Answer 2

He was likely looking for

• array_search — Searches the array for a given value and returns the corresponding key if successful

EDIT The question is somewhat odd for the given array. There is no point in doing this with anything else than PHP's native function. An alternative would be to use while, next, key and current if you'd wanted to it by hand. This still wouldn't explain why the interviewer noted you may not use recursion.

Answer 3

Since he said the array was pre-sorted, he was probably expecting a binary search. A linear search (with a possible optimisation since the array is sorted - exit with failure if you find a larger value) would of course be perfectly fine on the small array in the example. Probably faster, if it matters.

Answer 4

He probably was not looking for any specific answer. He probably wanted to see how you think and consider different options, and explaing their pros and cons, before choosing your way of implementing the thing.

Answer 5

The best approach is to use Binary search algorithm. Worst case complexity is o(logn)