Дана упорядоченная последовательность конечного числа элементов, так же известная в математике как «кортеж», (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):
- Сначала сравниваются крайние элементы множества. Если пересечение лежит внутри последовательности, т.е. $b больше крайнего «левого» элемента и меньше крайнего «правого» элемента множества $a, то происходит переход ко второму этапу. Иначе поиск завершается.
- Находим приблизительную середину множества $a (округление с приоритетом меньшего). Сравниваем «срединный» элемент $mdx с числом $b, тем самым понимая, какая «половина» множества нам нужна. Например $b > $mdx, следовательно нужно продолжить поиск во «второй», «большей» половине множества $a. Важно сохранять индексы при манипуляциях с массивом элементов.
- Рекурсивно повторяем поиск (читай п.1) до наступления профита.
В моём примере два раза получаются ключи множества, и хотя это происходит не всегда, такое поведение можно изменить. Я выбрал удобство получения «левого» и «правого» элементов множества и упростил понимание (прочтение) функции.
Может случится так, что на определённой итерации рекурсии в «срезе» массива останется только один элемент. Тогда, для получения двух «крайних» элементов, останется только одно значение. Эта ситуация учтена в коде функции, при её достижении «крайние» значения уравниваются.
В данной реализации не предусмотрена ситуация, когда элементы множества повторяются, что допустимо для кортежей. Результатом будет индекс верного значения элемента, но может и не первого, по приоритету индекса.