Бинарный поиск (Pascal)

[Peek-a-boo]

Моделирование работы планировщика потоков ОС.
Есть два массива - отсортированный по возрастанию массив с потоками (время, которое нужно программе на выполнение) и массив с ресурсами центрального процессора.
Программа должна расположить потоки из первого массива в порядке их обработки центральным процессором (Алгоритм выбора очередного потока на исполнение состоит в выборе потока, который имеет максимально близкое время работы к выделенному кванту времени). На выходе программы получается последовательность, которая задаёт порядок выполнения потоков центральным процессором.


Вся сложность в том, что поиск наиболее подходящего потока должен быть осуществлен способом под названием "Бинарный поиск". Пожалуйста, помогите.

[RUSt88]

почитай википедию, там толково написано про такой поиск

смотри, например, у нас имеется некая последовательность объектов (в нашем случае тип int)

1 5 6 0 9 12 -4 11 -7

нужно найти число F = 0

из этой последовательности нужно найти элемент (т.е. возвратить на него указатель допустим)

сначало нам нужно отсортировать этот массив
получим

-7 -4 0 1 5 6 9 11 12

теперь можно воспользоваться бинарным поиском
получаем длинну массива N
возьмем элемент в центре массива, т.е. c = (N % 2) = 8 % 2 = 4
сравним с икомым F
т.е. элемент массива под индексом 4 это число 5

а т.к. искомое число 0 и оно меньше 5, то ищем теперь в левой половине массива, т.е. среди элементов от нулевого индекса до 4-го
и так каждый раз обратно берем элемент из центра и сравниваем, если искомое больше чем в центре, то ищем правее, и наоборот


надеюсь понятно :DDD

[Peek-a-boo]

Да это то я конечно знаю. Дело в том, что нужно всегда выбирать наибольший из подходящих, к тому же, два раза один и тот же поток выбирать , естественно, нельзя. Конечно, можно запилить проверку, которая распознает, брали ли мы этот поток или нет, но тогда вся эффективность бинарного поиска (а именно - время его выполнения) сойдет на нет, разве не так?

[pray_driver]

RUSt88, да это вроде метод деления отрезка пополам

[RUSt88]

метод деления отрезка пополам

да? а пруф можно на бинарный поиск и на метод деления отрезка пополам?

или вы шутите?