Поиск ближайшего числа в последовательности

Дана упорядоченная последовательность конечного числа элементов, так же известная в математике как «кортеж», (a1,…,an). Все элементы этого множества — целые числа >= 0. Нужно написать функцию, которая на входе будет принимать два аргумента: указанное множество и один элемент, который является целым числом >= 0. На выходе функция должна возвратить индекс элемента множества, который равен указанному числу или наиболее близок к нему (в порядке декремента).

Пример работы функции на языке PHP может быть такой:

$a = array(1,3,4,5,7,13,14,18,20,24,25,29,30,33,51,78,99);
$b = 19;

function func($a, $b) {
    // тело функции
}

echo func($a, $b); // выведет "7" (индекс числа "18")

А вот сама функция:

function func($a, $b) {
    // проверяем, а было ли множество?
    if (!is_array($a)) return null;
    // это ключи/индексы множества
    $keys_arr = array_keys($a);
    // индекс "левого" элемента множества
    $ldx = array_shift($keys_arr);
    // индекс "правого" элемента множества
    $rdx = array_pop($keys_arr);
    // проверим чтобы индексы не закончились
    if (is_null($rdx)) $rdx = $ldx;
    // искомое число меньше или равно "левому" элементу 
    if ($b <= $a[$ldx]) return $ldx;
    // искомое число больше или равно "правому" элементу 
    if ($b >= $a[$rdx]) return $rdx;
    // индекс "срединного" элемента
    $mdx = ceil(count($a)/2);
    // снова получаем ключи множества
    // предыдущий массив ключей уже не полный
    $keys_arr = array_keys($a);
    // искомое число больше или равно "срединному" элементу
    if ($b >= $a[$keys_arr[$mdx]]) {
        // "срез" массива от "срединного" элемента (включительно)
        // и до конца
        return func(array_slice($a, $mdx, null, true), $b);
    }
    // а нет, искомое число меньше "срединного" элемента
    else {
        // "срез" массива от начала и до "срединного" элемента
        return func(array_slice($a, 0, $mdx, true), $b);
    }
}

Алгоритм работы функции очень похож на алгоритм быстрой сортировки (Quicksort):

  1. Сначала сравниваются крайние элементы множества. Если пересечение лежит внутри последовательности, т.е. $b больше крайнего «левого» элемента и меньше крайнего «правого» элемента множества $a, то происходит переход ко второму этапу. Иначе поиск завершается.
  2. Находим приблизительную середину множества $a (округление с приоритетом меньшего). Сравниваем «срединный» элемент $mdx с числом $b, тем самым понимая, какая «половина» множества нам нужна. Например $b > $mdx, следовательно нужно продолжить поиск во «второй», «большей» половине множества $a. Важно сохранять индексы при манипуляциях с массивом элементов.
  3. Рекурсивно повторяем поиск (читай п.1) до наступления профита.

В моём примере два раза получаются ключи множества, и хотя это происходит не всегда, такое поведение можно изменить. Я выбрал удобство получения «левого» и «правого» элементов множества и упростил понимание (прочтение) функции.

Может случится так, что на определённой итерации рекурсии в «срезе» массива останется только один элемент. Тогда, для получения двух «крайних» элементов, останется только одно значение. Эта ситуация учтена в коде функции, при её достижении «крайние» значения уравниваются.

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

Инструкции по теме:

Добавить комментарий