Нахождение индекса заданного значения в предварительно отсортированном массиве

Question

Сегодня я пошел на собеседование, и интервьюер спросил меня, как мне найти индекс заданного значения (числа) в предварительно отсортированном массиве, например:

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

Он также сказал, что использование рекурсии не допускается.

Я думаю, что функция должна выглядеть следующим образом:

* +1007 *

Как вы думаете, какое решение он ожидал от меня?

РЕДАКТИРОВАТЬ: Извините, я забыл добавить, что он первоначально просил меня написать псевдокод, но я сказал, что я не знаю. Затем я попытался написать его на PHP, но думаю, что он ожидает решения, не зависящего от языка.

Answer 1

Поскольку он сказал, что массив предварительно отсортирован, он, вероятно, ожидал двоичного поиска. Линейный поиск (с возможной оптимизацией, так как массив отсортирован - выход с ошибкой, если вы найдете большее значение), конечно, будет прекрасно работать с небольшим массивом в примере. Возможно, быстрее, если это имеет значение.

Answer 2

Он, вероятно, искал

• array_search - Выполняет поиск в массиве заданного значения и возвращает соответствующий ключ в случае успеха

РЕДАКТИРОВАТЬ Вопрос несколько странный для данного массива. Нет смысла делать это с чем-то еще, кроме нативной функции PHP. Альтернативой может быть использование while, next, key и current, если вы захотите сделать это вручную. Это по-прежнему не объясняет, почему интервьюер отметил, что вы не можете использовать рекурсию.

Answer 3

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

Answer 4

Лучший подход - использовать Алгоритм двоичного поиска . В худшем случае сложность o (logn)

Answer 5

Он, вероятно, не искал какого-либо конкретного ответа. Он, вероятно, хотел увидеть, как вы думаете, и рассмотреть различные варианты, и объяснить их плюсы и минусы, прежде чем выбрать способ реализации этой вещи.