бинарный поиск. поля с рекурсией. Опции

[lopata]

Бинарный поиск может быть применим на одно поле, в которое элемент сортировочно внесен.
Идея бинарного поиска состоит в том, чтобы сначала рассматривать средний элемент. Если он Искомый, тогда с успехом прерываете. Если не искомый, тогда можно через сравнение искомого элемента со средним установить, нужно ли в нижней или в верхней половине поля дальше искать. При каждом неудачном шаге поиска длина исследоваемой области (досягаемости) поля делится пополам.Это ведет к логарифмеческому Run-time:
при n элементах имеется 0(ld n) Шагов поиска.
Осуществите основе типа
TYPE
IntArray = array [...] of integer
рекурсивный алгоритм:
FUNCTION Contains (a :IntArray ; left,right : integer; x : integer) :BooLean;

который в сотрированном поле а внутри области [left...right] бинарно после значения х ищет и результат TRUE возвращает, когда х в поле оказывается.
Вышеуказанная фунукция использует call by value.

не совсем понимаю задания. очень туго доходит. хотя уверена что когда 2 строчки.

[volvo]

сам бинарные деревья в принципе понимани.

А причем тут бинарные деревья? Они к бинарному поиску никакого отношения не имеют...

Задача твоя - в том, чтобы получить массив (для бинарного поиска нужно, чтобы этот массив был упорядоченным, т.е., отсортированным, иначе этот метод не работает), и в этом массиве найти заданный элемент (или не найти его, это уж как повезет). Как это делается:

1. Поскольку решение тебе надо рекурсивное - то начинаем с условия окончания (странно, правда? Но так оно и делается, с этого начинается разработка любой рекурсивной подпрограммы, иначе зациклишь ее, и даже не заметишь). Итак. Что будет условием окончания? Когда поиск должен закончиться? Все просто: Когда Right + 1 = Left, то есть, между Right и Left нет других элементов. Тогда можно считать, что мы дошли до конца, и больше рекурсия продолжаться не будет.

Если это условие:

if Right = Left + 1 then 

выполняется, то остается проверить, равен ли элемент A[ Left ] или A[ Right ] заданному. Если равен - вернуть True, если нет - вернуть False.

2. Если между индексами Left и Right есть еще элементы, то надо найти середину (среднее арифметическое), и вызывать функцию рекурсивно, вместо Right или Left подставляя значение этой середины.

Вот и все, собственно. Попробуй по написанному здесь объяснению написать код. Хотя бы его начало. Что не понятно, или не получается - говори. Задача действительно решается в несколько строк.

P.S. Поиском, значит, опять не пользуемся. Ну-ну... Потом расскажу, откуда я узнал об этом...