Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Поиск в массиве

Страницы: < 1 2 3
selesasha © (2012-03-15 14:26:00)
Дано:
1) Неубывающий массив повторяющихся данных, длинной ~15000 возможно имеющий nil среди значений, и почти наверняка имеющий хвост из nil в конце
2) Массив находится на удаленном сервере, каждый запрос одного элемента это post через http с последующим парсингом ответа. Т.е. Чтобы сравнить 2 элемента массива нужно сделать 2 запроса.
3) Функция позволяющая для пары данных однозначно определить какой из аргументов больше, или их равенство, если ни одно из них не nil

Задача:
Найти границы окна, внутри котрого находится значение заданное пользователем, за наименьшее число обращений к серверу. Найти не обязательно точно, возможна погрешность, максимальнывй размер которой задается пользователем, при этом пользователь может указать погрешность 0.

Поделитесь пожалуйста своими соображениями. Код никакой не прошу, только идеи и Ваши умные мысли.

selesasha (2012-03-15 17:39:00) [41]
В чем идиотизм?

Jeer (2012-03-15 17:36:00) [42]
Очередная идиотская задача.

selesasha (2012-03-15 17:34:00) [43]

> Как соотносится "Неубывающий массив" и наличие nil - посередине,
> что ли, где попало?

Именно. Сами данные неубывающие, но некоторые элементы массива данных не содержат.

> А если один из элементов - nil, что вернет функция?

Вызовется эксепшн.

> А так, всё просто - методом последовательных приближений
> - узнаешь значение в середине массива, и дальше хватаешь
> элемент из середины остатка.

бинарный поиск тут не подходит - по крайней мере в лоб:
1) Какой поддиапазон выбирать если середина отрезка - nil?
2) Как находить границы окна, если середина отрезка попала в искомое значение?

Cobalt (2012-03-15 15:44:00) [44]
А если один из элементов - nil, что вернет функция?

А так, всё просто - методом последовательных приближений - узнаешь значение в середине массива, и дальше хватаешь элемент из середины остатка.

MBo (2012-03-15 14:47:00) [45]
Как соотносится "Неубывающий массив" и наличие nil - посередине, что ли, где попало?

Страницы: < 1 2 3

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »