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

[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 строчки.

[lopata]

сам бинарные деревья в принципе понимани.
но непонятно что это за параметры левый и правый целового типа

[Archon]

Не следует путать простой бинарный поиск и бинарное дерево поиска. В твоем случае дерево строить не надо. Достаточно приведенной рекурсивной функции.

Параметры left и right - это начало и конец участка, внутри которого производится поиск. То есть сперва на место этих параметров подставляются начало и конец массива. Если элемент в середине отрезка не найден, функция должна вызвать саму себя (рекурсия), подставив на место left и right новые значения (а именно начало и конец той половины начального участка, в которой следует искать дальше).

PS Кстати, странно: в функции не предусмотрена возможность вернуть в программу найденный элемент.

[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. Поиском, значит, опять не пользуемся. Ну-ну... Потом расскажу, откуда я узнал об этом...

[lopata]

Все, товарищи, спасибо. Дико ступила. стыдно

[lopata]

Ошибка использования BB кодов форума. Возможно вы неправильно использовали какой-то из тэгов, как, например, тэг [TAG], тогда как он должен использоваться в виде [TAG=] или наоборот.
//
Не хочет код писать/

Добавлено через 13 мин.

FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR m: integer;
BEGIN
IF (R+1)= L
   THEN
       BEGIN
       IF (x=a[r])or (x=a[l])THEN Contains := TRUE
          ELSE
              BEGIN
              m := r+(l-r)div 2;
              IF x=a[m] THEN Contains := TRUE
                 ELSE
                     IF x> a[m] THEN BEGIN
                        r := m+1;
                        Contains := Contains(a,l,r,x)
                     END
                     ELSE BEGIN
                          l := middle-1;
                          Contains := Contains(a,l,r,x)
                     END;
END;
END;

Добавлено через 52 сек.
пришлось сократить\

[lopata]

Не. не правильно..
вот кое-что изменила:

FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR M: integer;
BEGIN
IF (R+1)= L THEN
   BEGIN
        IF (x=a[r])or (x=a[l])THEN Contains := TRUE
           ELSE Contains := FALSE
END
   ELSE
       BEGIN
       m := r+(l-r)div 2;
       IF x=a[m] THEN Contains := TRUE
          ELSE BEGIN
               IF x> a[m] THEN BEGIN
                  r := m+1;
                  Contains := Contains(a,l,r,x)
               END
                  ELSE BEGIN
                       l := m-1;
                       Contains := Contains(a,l,r,x)
                  END;

       END;
END;

l = left
r = right
m = middle
И еще почему в dev pascal ругается что overloaded identifier Contains isn't a function

[Archon]

И все-таки неправильно. Покажи целиком программу, в которой ты тестируешь эту функцию. Заодно будет проще понять, почему dev pascal ругается =)

Добавлено через 4 мин.
Первое, что бросилось в глаза:

IF (R+1)= L THEN

Путаешь право и лево. Так ты никогда из рекурсии не выйдешь.

Добавлено через 15 мин.
Ух, да у тебя по всей программе так. Но даже если поменять их местами, твой алгоритм порой выходит за границы исходного интервала. Например, на следующих исходных данных:

. . .
var
	Arr: array[1..3] of Integer = (1, 2, 4);
begin
	Contains(Arr, 1, 3, 6);
end.

[lopata]

Archon, честно говоря не совсем понимаю о чем ты

[Archon]

Ну смотри:
L - это же Left (левая граница интервала), верно?
R - тогда соответственно Right (правая граница).
То есть L < R. Тогда как R + 1 может равняться L?

[lopata]

аха, это поняла...наоборот

Добавлено через 1 мин.
поняла. счас исправлю..действительно по всей программе то же самое

Добавлено через 2 мин.
А с остальным что не так?

[Archon]

А ты проверь с приведенным выше массивом. Там всего 3 элемента - можно и в уме сделать.

[lopata]

все равно не понимаю/

[Archon]

На приведенных мной исходных данных функция из рекурсии никогда не выйдет. Если в уме не получается, запусти программу и убедись.

Добавлено через 4 мин.
И вообще будет выход за границы массива.

[lopata]

это я уже поняла...
тогда нужно поставить условие

while left<= right do

вроде
я запуталась/

Добавлено через 7 мин.
и нифига это тогда не рекурсия получется

[lopata]

алилуя...
или очередное заблуждение или просвет :

FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR M: integer;
BEGIN
IF l <> r THEN
   BEGIN
       m := l+(r-l)div 2;
       IF x=a[m] THEN Contains := TRUE
          ELSE BEGIN
               IF x> a[m] THEN BEGIN
                  l := m+1;
                  Contains := Contains(a,l,r,x)
               END
                  ELSE BEGIN
                       r := m-1;
                       Contains := Contains(a,l,r,x)
                  END;
          END;
   END
ELSE
   BEGIN
        IF (x=a[r])or (x=a[l])THEN contains := TRUE ELSE   contains := FALSE
   END

END;

[Archon]

Ну, не совсем =) Лучше было бы так сделать:

FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR M: integer;
BEGIN
    IF (l+1) = r THEN
    BEGIN
        IF (x=a[r])or (x=a[l])THEN Contains := TRUE
        ELSE Contains := FALSE;
    END
    ELSE
    BEGIN
        m := l+(r-l)div 2;
        { Проверку x=a[m] тоже убрал, так как на следющем шаге рекурсии этот }
        { элемент станет границей и все равно проверится                     }
        IF x> a[m] THEN BEGIN
            l := m; { Тут убрал "+1" }
            Contains := Contains(a,l,r,x)
        END
        ELSE BEGIN
            r := m; { Тут убрал "-1" }
            Contains := Contains(a,l,r,x)
        END;
    END
END;

Сравни со своей старой версией.

Но это один из вариантов решения: тот, который описал volvo. Если брать строго тот алгоритм, что приведен в задании, получится так:

function Contains (a: IntArray; l, r: Integer; x: Integer): Boolean;
var
	m: Integer;
begin
	if l > r then
		Contains := False
	else begin
		m := l + (r - l) div 2;
		if x = a[m] then
			Contains := True
		else if x < a[m] then
			Contains := Contains(a, l, m - 1, x)
		else
			Contains := Contains(a, m + 1, r, x);
	end;
end;

Ищи отличия

[volvo]

    IF (l+1) = r THEN
    BEGIN
        IF (x=a[r])or (x=a[l])THEN Contains := TRUE
        ELSE Contains := FALSE;
    END

лучше заменить на

if L + 1 = R then
  Contains := (x=a[R]) or (x=a[L])

, вместо включения еще одного условия...

И еще почему в dev pascal ругается что overloaded identifier Contains isn't a function

Dev-Pascal это оболочка. Компилятор, который там используется (если я не ошибаюсь, давно его использовал) - FPC. В каком режиме совместимости ты компилируешь программу, что у тебя возникает такая ошибка (и заодно - какая версия компилятора? Вполне возможно, что тебе надо ее просто обновить)? Ты часом не пытаешься эту функцию в модуле (в Unit-е, в смысле) описывать?

[lopata]

Dev-Pascal это оболочка. Компилятор, который там используется (если я не ошибаюсь, давно его использовал) - FPC. В каком режиме совместимости ты компилируешь программу, что у тебя возникает такая ошибка (и заодно - какая версия компилятора? Вполне возможно, что тебе надо ее просто обновить)? Ты часом не пытаешься эту функцию в модуле (в Unit-е, в смысле) описывать?

1.9.2.
неа. не в модуле.


Добавлено через 4 мин.
а по поводу совместимости не знаю что сказать/

[volvo]

1.9.2.

Уже 2.2.4 на дворе... Ты б скачала новую версию FPC, и прямо там бы работала, зачем тебе этот DevPascal нужен?