Алгоритм быстрого поиска

@nniikkyy · Регистрация: 15.06.2012

Студворк — интернет-сервис помощи студентам

Ребят, помогите, кто чем может, для курсовой очень надо((
если есть какие-то предложения, пишите здесь [только здесь]

алгоритм быстрого поиска...опять же код есть, но не рабооотает(

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
program Poisk3a;
  var A:array[1..100] of integer;
  N,X,left,right,i:integer;
 begin
  read(N); {N<=100}
  write('введите упорядоченный по возрастанию массив');
  for i:=1 to N do read(A[i]);
  read(X);
  left:=1; right:=N;
  {левая и правая граница фрагмента для поиска}
  while left begin
    c:=(left + right) div 2;
    {середина с округлением в меньшую сторону}
    if X>A[c] then
    {если массив упорядочен по убыванию, то if X left:=c+1
    {выбираем правую половину без середины, меняя left}
    else right:=c;
    {выбираем левую половину с серединой, меняя right}
  end;
  if X=A[left] then {здесь left = right, но не всегда = c}
   write('первое вхождение числа ',X,' в массив A на ',left,' месте')
  else write('не нашли');
end.

@H@ker · 18.06.2012, 21:36

nniikkyy, лучше задание напиши - в коде сложнее разбираться.

@nniikkyy · 18.06.2012, 21:48 **[ТС]**

вобще мне нужно написать алгоритм быстрого поиска на free pascal и описать что как работает

@H@ker · 18.06.2012, 21:50

А что это вообще за зверь - "алгоритм быстрого поиска"?

@nniikkyy · 18.06.2012, 21:52 **[ТС]**

H@ker, вот здесь хорошо написано: ftp://po.istu.ru/public/docs/o... earch.html
жаль, что код на си там только)

@H@ker · 18.06.2012, 22:22

nniikkyy, эх, видно, не для школьного уровня. Для меня знакомым словосочетанием там было только : "поиск подстроки в строке", но для этого ведь есть функции для работы со строками, зачем что-то изобретать? Все равно, думаю, без них не обойдется? Или нужно представлять строку как массив и перебирать каждый символ до момента совпадения подстроки со строкой?

@Dani · 18.06.2012, 22:29

H@ker, стандартная функция медленная, а, например, КМП - гораздо быстрее.

@nniikkyy · 18.06.2012, 22:36 **[ТС]**

ну такая вот тема для курсовой "исследование алгоритмов поиска, реализация алгоритма быстрого поиска, алгоритм боуэра мура, алгоритм быстрого поиска, алгоритм оптимального несовпадения
"

@H@ker · 18.06.2012, 22:40

Dani, не поможете ли nniikkyy?) Мне просто интересно, как бы вы это решили.

@nniikkyy · 19.06.2012, 10:52 **[ТС]**

а мне то как интересно...

@Dani · 19.06.2012, 11:10

nniikkyy, у вас код - алгоритм БИНАРНОГО (быстрого) поиска в упорядоченом массиве, ссылка - поиск подстроки в строке. Что из них вам надо?

Добавлено через 7 минут

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
type mas = array [1..10001] of longint;
 
 
 
function bin_search (a: mas; n: longint): boolean;
var l,r,m: longint;
begin
l:= 0; r:= n+1; 
 
while r-l>1 do
begin
m:= (l+r) div 2;
if a[m]>n then r:= m
else l:= m;
end; 
 
bin_search:= n=a[l];
end;

Я написал функцию.

@nniikkyy · 19.06.2012, 11:12 **[ТС]**

нужен пример любого алгоритма быстрого поиска.

@Dani · 19.06.2012, 11:16

В число в массиве или подстроку в строке?
Тут - число в массиве, и оно работает за O (lg₂ N)

@nniikkyy · 19.06.2012, 11:25 **[ТС]**

ну это же алгоритм быстрого поиска, значит мне подходит)

Добавлено через 39 секунд
а вобще подстроку в строке...

@Dani · 19.06.2012, 11:32

Алгоритм двоичного поиска в массиве необходим для быстрого поиска числа в отсортированном массиве. На каждом этапе поиска массив делится на 3 части - 1 одна часть содержит числа меньшие текущего, другая - числа большие текущего, а 3 - само текущее число. На каждом этапе, за текущее число берется среднее число. Пример:
надо найти 1.
Массив:
числа 1 3 4 5 7
номера 1 2 3 4 5.
Текущее числа - середина, (1+5) div 2 = 3. Т.к. 4 (это третье число) > 1, то ищем в левой части, потому что там находятся числа, меньшие, чем 4.

Теперь массив:
числа 1 3
номера 1 2
Текущее число - середина, то (1+2) div 2 = 1. Т.к. 1=1, то выходим из поиска.

@Paster Fob · 19.06.2012, 17:12

посмотри Песни о Паскале глава 42,в книге всё подробно описано.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@H@ker 19 / 19 / 17 Регистрация: 25.04.2012 Сообщений: 138
	18.06.2012, 21:36
	nniikkyy, лучше задание напиши - в коде сложнее разбираться. 0

@nniikkyy 1 / 1 / 2 Регистрация: 15.06.2012 Сообщений: 21
	18.06.2012, 21:48 [ТС]
	вобще мне нужно написать алгоритм быстрого поиска на free pascal и описать что как работает 0

@H@ker 19 / 19 / 17 Регистрация: 25.04.2012 Сообщений: 138
	18.06.2012, 21:50
	А что это вообще за зверь - "алгоритм быстрого поиска"? 0

@nniikkyy 1 / 1 / 2 Регистрация: 15.06.2012 Сообщений: 21
	18.06.2012, 21:52 [ТС]
	H@ker, вот здесь хорошо написано: ftp://po.istu.ru/public/docs/o... earch.html жаль, что код на си там только) 0

@H@ker 19 / 19 / 17 Регистрация: 25.04.2012 Сообщений: 138
	18.06.2012, 22:22
	nniikkyy, эх, видно, не для школьного уровня. Для меня знакомым словосочетанием там было только : "поиск подстроки в строке", но для этого ведь есть функции для работы со строками, зачем что-то изобретать? Все равно, думаю, без них не обойдется? Или нужно представлять строку как массив и перебирать каждый символ до момента совпадения подстроки со строкой? 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	18.06.2012, 22:29
	H@ker, стандартная функция медленная, а, например, КМП - гораздо быстрее. 0

@nniikkyy 1 / 1 / 2 Регистрация: 15.06.2012 Сообщений: 21
	18.06.2012, 22:36 [ТС]
	ну такая вот тема для курсовой "исследование алгоритмов поиска, реализация алгоритма быстрого поиска, алгоритм боуэра мура, алгоритм быстрого поиска, алгоритм оптимального несовпадения " 0

@H@ker 19 / 19 / 17 Регистрация: 25.04.2012 Сообщений: 138
	18.06.2012, 22:40
	Dani, не поможете ли nniikkyy?) Мне просто интересно, как бы вы это решили. 0

@nniikkyy 1 / 1 / 2 Регистрация: 15.06.2012 Сообщений: 21
	19.06.2012, 10:52 [ТС]
	а мне то как интересно... 0

@nniikkyy 1 / 1 / 2 Регистрация: 15.06.2012 Сообщений: 21
	19.06.2012, 11:12 [ТС]
	нужен пример любого алгоритма быстрого поиска. 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	19.06.2012, 11:16
	В число в массиве или подстроку в строке? Тут - число в массиве, и оно работает за O (lg₂ N) 0

@nniikkyy 1 / 1 / 2 Регистрация: 15.06.2012 Сообщений: 21
	19.06.2012, 11:25 [ТС]
	ну это же алгоритм быстрого поиска, значит мне подходит) Добавлено через 39 секунд а вобще подстроку в строке... 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	19.06.2012, 11:32
	Алгоритм двоичного поиска в массиве необходим для быстрого поиска числа в отсортированном массиве. На каждом этапе поиска массив делится на 3 части - 1 одна часть содержит числа меньшие текущего, другая - числа большие текущего, а 3 - само текущее число. На каждом этапе, за текущее число берется среднее число. Пример: надо найти 1. Массив: числа 1 3 4 5 7 номера 1 2 3 4 5. Текущее числа - середина, (1+5) div 2 = 3. Т.к. 4 (это третье число) > 1, то ищем в левой части, потому что там находятся числа, меньшие, чем 4. Теперь массив: числа 1 3 номера 1 2 Текущее число - середина, то (1+2) div 2 = 1. Т.к. 1=1, то выходим из поиска. 0

@Paster Fob 296 / 274 / 194 Регистрация: 03.05.2012 Сообщений: 570
	19.06.2012, 17:12
	посмотри Песни о Паскале глава 42,в книге всё подробно описано. 0