Быстрый поиск в массиве, алгоритм быстрого поиска Опции

[Белоснежка]

Помогите с задачей. Искала в поисковиках, в книжках с алгоритмами но ничего не нашла
Нужно программку которая производит быстрый поиск (при помощи алгоритма быстрого поиска) заданной буквы в массиве из заданного количества элементов
Я уже все что можно перечитала нигде про алгоритм быстрого поиска ничего не нашла.
Ребятки может кто-то знает? Помогите а?

[Ozzя]

http://algolist.manual.ru/search/index.php

[andriano]

Думаю, "быстрый поиск" не является общеупотребительным термином.
Поэтому нужно определиться, что именно искать и при каких условиях.
Если, например, нужно найти что-то в отсортированном массиве, целесообразно применить бинарный поиск, а если нужно найти объект в базе сразу по нескольким классифицирующим признакам, то можно посмотреть:
http://www.web-brodilka.ru/lesson.php?part=5&num=24

[Белоснежка]

Вот я нашла но этот кодя никак не смогла довести до рабочего состояния. Мне нужно чтоб поиск был по буквам а это кажется ищет цифры. Но алгоритм именно то что мне нужен там 2 варианта.

Код

program Poisk3a;
var A:array[1..100] of integer;
N,X,left,right: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.

ПРИМЕР: Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X.


program Poisk3b;
var A:array[1..100] of integer;
N,X,left,right:integer;
{функция считает сумму цифр числа a, здесь a - локальная переменная}
function Sum(a:integer):integer;
var s:integer;
begin
s:=0; a:=abs(a);
while a>0 do
begin
s:=s + a mod 10;
a:=a div 10;
end;
Sum:=s;
end;
begin
read(N); {N<=100}
write('введите массив, упорядоченный по возрастанию сумм цифр');
{например, для N=4 : 122, -432, 88, 593}
for i:=1 to N do read(A[i]);
read(X);
left:=1; right:=N;
{левая и правая граница фрагмента для поиска}
while left
begin
c:=(left+right+1) div 2;
{середина с округлением в большую сторону}
if X>=Sum(A[c]) then left:=c
{выбираем правую половину с серединой, меняя left}
else right:=c-1;
{выбираем левую половину без середины, меняя right}
end;
if X=Sum(A[left]) then {здесь left = right, но не всегда = c}
write('последнее число с суммой цифр=',X,' равно',A[left], ' находится в массиве A на ',left,' месте')
else write('не нашли');
end.

[Белоснежка]

Может кто сможет переделать?

[spill]

Буквы почти ни чем не отличаются от цифр (с точки зрения этой задачи). Поэтому если ты везде заменишь тип integer на char, то все должно работать.
Кстати, эту строчку:

Код

var A:array[1..100] of integer;

(это сортируемый массив) можно заменить на A: String (в нескольких местах). Тогда будет сортироваться строка.
Другой вопрос, если нужно отсортировать записи с ключем типа символ. Это делается по-другому. Ты опиши поподробнее, что именно нужно сделать.

[volvo]

(это сортируемый массив) можно заменить на A: String (в нескольких местах). Тогда будет сортироваться строка.

Насколько я вижу, тут вообще нет речи о сортировке, следовательно никакая строка сортироваться не будет. К строке будет применяться алгоритм бинарного поиска - это да... Только надо бы подправить программу, иначе она не то что работать - она и компилироваться не будет...

program Poisk3a;
var
  A: string;
  midd, left, right:integer;
  X: char;
begin
  write('Введите упорядоченную строку: '); readln(A);
  Write('Что будем искать? '); readln(X);

  left:=1; right:=length(A);
  while (Right - Left) > 1 do begin
     midd := (right + left) div 2;
     if X <= A[midd] then right := midd else left := midd
  end;

  midd := -1;
  if X = A[ left ] then midd := left
  else
    if X = a[ right ] then midd := right;

  if midd <> -1 then
    write('символ с индексом ', midd ,' является: ', X)
  else write('искомый символ не найден');
end.

[spill]

Прошу прощения, я перепутал...

[Белоснежка]

Ой большое спасибо!
Я вот что нашла ...Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой.
Это значит тут гдето надо просто поменять < на >
Случайно не здесь if X <= A[midd] then right := midd else left := midd ?

[volvo]

Случайно не здесь if X <= A[midd] then right := midd else left := midd ?

Угу, здесь... Только не поменять знак, а убрать "=" (сделать "строго меньше"), тогда будет находиться последнее вхождение.