Форум программистов, компьютерный форум, киберфорум
Наши страницы
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.90/30: Рейтинг темы: голосов - 30, средняя оценка - 4.90
simon140906
2 / 2 / 1
Регистрация: 06.04.2010
Сообщений: 52
#1

Двоичный(бинарный) поиск

17.05.2010, 21:31. Просмотров 5512. Ответов 5
Метки нет (Все метки)

Доброго времени суток,коллеги =) Возникла у меня проблема - написал программу,реализующую двоичный поиск,а препод говорит,что неправильно)) и не говорит,где ошибка >___<
Проверьте пожалуйста=)
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
program dvoichn_poisk;
uses crt;
var  a: array [1..16] of integer;
    g,m,i,h,k,n,l,j,smena,kol,centr,d:integer;
     flag:boolean;
     label 1,2,3;
 
begin
clrscr;
randomize; kol:=0;
for i:=1 to 16 do
    begin
    a[i]:=0;
    end;
for i:=1 to 16 do
    begin
    a[i]:=random(100);
    writeln(a[i]);
    end;
3: for h:=0 to 17 do begin
   for m:= 0 to 17 do
       begin if a[m]<a[m-1] then
       begin smena:=a[m-1]; a[m-1]:=a[m]; a[m]:=smena; end;
       end;
       end;
{for g:=1 to 16 do
    begin
    write (a[g],' ');
    end;}
writeln('vvedite argument poiska');
readln(k); l:=0; flag:=false; centr:=a[8]; d:=8;
if k=centr then begin kol:=kol+1; goto 1; end;
if k<centr then begin kol:=kol+1; d:=4; centr:=a[d];
           if k=centr then begin kol:=kol+1; goto 1; end;
           if k<centr then begin kol:=kol+1; d:=2; centr:=a[d];
                      if k=centr then begin  kol:=kol+1; goto 1; end;
                      if k<centr then begin kol:=kol+1;d:=1; centr:=a[d]; end;
                      if k>centr then begin kol:=kol+1;d:=3; centr:=a[d]; end;
                      end;
           if k>centr then begin kol:=kol+1; d:=6; centr:=a[d];
                   if k=centr then begin kol:=kol+1; goto 1; end;
                   if k<centr then begin kol:=kol+1;d:=5; centr:=a[d]; end;
                   if k>centr then begin kol:=kol+1;d:=7; centr:=a[d]; end;
                   end;
                end;
if k>centr then begin kol:=kol+1;d:=12; centr:=a[d];
           if k=centr then begin kol:=kol+1; goto 1 ;end;
           if k<centr then begin kol:=kol+1; d:=10; centr:=a[d];
                   if k=centr then begin kol:=kol+1; goto 1; end;
                   if k<centr then begin kol:=kol+1;d:=9; centr:=a[d]; end;
                   if k>centr then begin kol:=kol+1;d:=11; centr:=a[d]; end;
                end;
           if k>centr then begin kol:=kol+1; d:=14; centr:=a[d];
                   if k=centr then begin kol:=kol+1; goto 1; end;
                   if k<centr then begin kol:=kol+1; d:=13; centr:=a[d]; end;
                   if k>centr then if k=a[15] then begin kol:=kol+1; d:=15; end;
                                   if k=a[16] then begin kol:=kol+1; d:=16 end;
                                   end;
                 end;
 
 
 
{for j:=1 to 16 do
begin
l:=l+1;
if k=a[j] then begin flag:=true; goto 1; end;
end;}
{if flag=false then begin writeln ('poisk zavershen  ne udachno');
   writeln ('chislo sravnenii = ',l); end;}
 
1: if k=a[d] then begin writeln ('poisk zavershen udachno');
   writeln ('chislo sravnenii = ', kol); end;
if k<>a[d] then begin  writeln('poisk zavershen ne udachno');
   writeln ('chislo sravnenii = ', kol); end;
readln;
end.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2010, 21:31
Ответы с готовыми решениями:

Двоичный поиск
Задание: Реализуйте алгоритм бинарного поиска. Входные данные: В первой...

Бинарный поиск в матрице
Матрица упорядочена по столбцам по не убыванию. Как можно реализовать...

задание на бинарный поиск
Используя бинарный поиск элементов в массиве найти на каком месте находится...

Последовательный и бинарный поиск
нужно сделать 2 программы: 1)которая осуществляет последовательный поиск(без...

Добавить бинарный поиск
Программа готова, просто добавить этот &quot;ужасный&quot; бинарный поиск если нужно...

5
lera8
634 / 217 / 63
Регистрация: 03.11.2009
Сообщений: 488
17.05.2010, 21:37 #2
эм ваша программа двоичного поиска как то странно выглядит..Это вам я так понимаю в массиве найти заданный элемент?
1
simon140906
2 / 2 / 1
Регистрация: 06.04.2010
Сообщений: 52
17.05.2010, 21:44  [ТС] #3
И если кто может,объясните нубу человеческим языком,что творится тут

Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.

Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел
1 2 3 4 5. Здесь средним элементом является 3. Это значени.

меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел
4 5. На следующем шаге нужный элемент будет найден. При дво.

ичном поиске число сравнений в худшем случае равно
log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.

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

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function BSearch (item: DataArray; count:integer;                             
key:DataItem):integer;     
var       low, high, mid: integer;       
found:boolean;     
begin       
low:=1; 
high:=count;       
found:=false;         { не найден }      
 while (low<=high) and (not found) do       
begin         
mid:=(low+high) div 2;         
if key<item[mid] then high:=mid-1         
else if key>item[mid] then low:=mid+1        
 else found:=true;  { найден }       
end;       
if found then BSearch:=mid       
else BSearch:=0;  { не найден }    
 end; { конец поиска }
взято с http://www.cyberguru.ru/programming/...ia-page19.html

Добавлено через 33 секунды
Цитата Сообщение от lera8 Посмотреть сообщение
эм ваша программа двоичного поиска как то странно выглядит..Это вам я так понимаю в массиве найти заданный элемент?
да-да =) в массиве)
0
lera8
634 / 217 / 63
Регистрация: 03.11.2009
Сообщений: 488
17.05.2010, 21:47 #4
ну вот код двоичного поиска, все в принципе просто, у вас хорошая теория найдена
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var
a: array [1..20] of integer;
i,j,x,n,c,nx,r,l:integer;
flag:boolean;
begin
  writeln('Введите размер и элемет для поиска');
  readln(n,x);
    writeln('Исходный массив');
   for i:=1 to n do
     begin
       a[i]:=random(250)-27;
       write(a[i]:4);
     end;
      writeln;
     i:=0;
   repeat
       i:=i+1;
       flag:=false;
     for j:=n-1 downto i do
        if a[j] > a[j+1] then begin
          c:=a[j]; a[j]:=a[j+1]; a[j+1]:=c; flag:=true;
        end;
   until not flag;
   nx:=0; l:=1; r:=n;
    while l <= r do begin
     c:=(l+r) div 2;
     if x=a[c] then begin
       nx:=c; r:=l-1;
     end;
     if x > a[c] then r:=c-1;
     if x < a[c] then l:=c+1;
   end;
     writeln('Отсортированный массив');
    for i:=1 to n do
      write(a[i]:4);
    if nx=0 then writeln('Не найден')
    else  writeln('Числу x',x,'равен элемент',a[nx])
end.
1
simon140906
2 / 2 / 1
Регистрация: 06.04.2010
Сообщений: 52
17.05.2010, 21:48  [ТС] #5
огромное спасибо вам, очень большое)))
1
lera8
634 / 217 / 63
Регистрация: 03.11.2009
Сообщений: 488
17.05.2010, 21:49 #6
а если что у меня массив заполняется случайными числами исправьте если хотите явно убедиться что правильно работает, а написана это прога без процедур

Добавлено через 20 секунд
Пожалуйста)
1
17.05.2010, 21:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2010, 21:49

Бинарный поиск в типизированном файле
function bsearch(var search:LongInt;var f:tfile ):Boolean; var ...

Бинарный поиск. В массиве A(N) найти элементы, принадлежащие диапазону [М, К]
В массиве A(N) найти элементы, принадлежащие диапазону .

В отсортированном массиве произвести бинарный поиск индекса элемента со значением K
Дан линейный целочисленный массив из N элементов. Отсортировать элементы...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru