Търсене на елемент

 Задачата за „търсене" на елементи в даден масив може да бъде определена по следния начин:

Да се намери онзи елемент от даден масив, който е в релация ρ спрямо отнапред зададен елемент а*. Релацията ρ може да бъде една от следните шест: <, ≤, =, ≠, ≥, >. Понякога се налага да бъдат търсени всичките елементи, които удовлетворяват зададеното условие, но описаните по-долу алгоритми разглеждат първия случай. Разбира се, необходими са малки промени в описанието на дадените алгоритми, за да бъдат валидни и във втория случай.

1. Алгоритъм за последователно търсене

Нека А е едномерен масив с n елемента. Започвайки от първия елемент а₁ последователно се преглеждат следващите елементи от масива А до намирането на търсения или до изчерпването на всички елементи, без да бъде намерен търсеният документ. Очевидно процедурата е много проста за изпълнение но тя „заплаща" с малката си скорост. Методът на последователното търсене може да бъде ефективен само за малки стойности на n.

Алгоритъм S

S1. [Начален номер на проверявания елемент.] i:=1

S2. [Сравнение.] Ако A_i е в релация ρ спрямо а*, изпълнете S5

S3. [Определяне номера на следващия елемент.] i: = i+1

S4. [Има ли още елементи?] Ако 1≤n, изпълнете S2

S5. [Край.] Прекратете търсенето.

Търсенето се извършва последователно, като се започне от първия елемент до намиране на елемент, равен на В или до намиране на индекс j при който Аj>В.

Блок-схема на алгоритъма:

2. Търсене на елемент в подреден масив (двоично търсене)

Даден е маснв А с N числени елемента, N>1, подредени по големина в растящ ред. Дадено е и числото b. Да се провери има ли сред елементите на А равен на b. Ако има, да се съобщи неговият индекс, ако не - да се издаде подходящо съобщение.

Идея на алгоритъма: масивът се разделя на две части и се преценява в коя част би могъл да бъде елементът b. С тази част се постъпва по същия начин, както с целия масив. Така се действа, докато се открие елементът b или се стигне до два елемента, за които е в сила А_j<b и b<А_j+1, което означава, че b не се съдържа в масива А.

Ще предполагаме, че релацията за сравнение е равенство и че масивът А е предварително подреден по възходящ ред на елементите си, т. е. a₁≤a₂≤a₃≤…≤a_n.

Ако търсеният елемент е b, веднага може да се определи в коя от двете половини на масива А той не се намира. За целта е досатъчно да се сравнят b и а_k, където . По този начин броят на елементите, в които се извършва търсенето, след едно сравнение намалява наполовина. С подходящата част от двете части на масива се постъпва по същия начин, т.е. разделя се отново на две равни части и т.н.  Това продължава, докато се намери търсеният елемент или се установи, че такъв елемент в масива няма. Точното описание е следното.

Алгоритъм В

B1. [Начални граници на масива.] i: = 1,.j:=n

B2. [Пресмятане „средата” на масива.]

B3. [Сравнение.] Ако а_k=b, изпълнете В8

B4. [Сравнение.] Ако a_k<b, изпълнете В6

В5. [Нова дясна граница на масива.] j:=k-1, изпълнете В7

B6. [Нова лява граница на масива.] i:=k+1

B7. [Проверка за край.] Ако i≤j, изпълнете В2

B8. [Край.] Прекратете търсенето.

Пример A=(3, 5, 6, 6, 10, 15, 16, 17, 90, 99), b=15, n=10

Разгледаният масив в примера е много малък, за да бъде добре осъзната голямата скорост на търсене по алгоритъм В. Това по-добре може да се види, ако се пресметне максималният брой сравнения, които се извършват при двоичното търсене. Нека е даден масив с n елемента и l е такова цяло положително число, че:

Преди да се извърши първото сравнение, броят на елементите, измежду които е възможно да се намира търсеният елемент, е равен на n. След първото сравнение този брой е вече , след второто е , а след (l-1)-то сравнение ще бъде т. е един елемент. Следователно, необходимо е още най-много едно сравнение (т. е. общо най-много l), за да се намери търсеният елемент или да се установи, че такъв елемент няма. По условие , откъдето чрез логаритмуване следва: 0≤log₂n – log₂2 ^l-1<1, т. е. l-1≤ log₂n.

Окончателно се получава l≤[log₂n]+1.

Да разгледаме отново алгоритъм I (подреждане чрез “вмъкване”). Точка I3 указва, че елементът а_k+1 трябва да намери мястото си между първите k вече подредени елементи. С други думи, това е задача за търсене в нареден масив и следователно може да се използува алгоритъм В. Това е само един пример, който показва, че подреждането и търсенето са две взаимно свързани дейности. Ние подреждаме, за да търсим по-бързо, но като подреждаме, се налага да търсим. Във всички изложени дотук алгоритми за подреждане и търсене се предполагаше, че елементите в масива са наредени един след друг. Ако структурата на масива е друга, естествено тогава и алгоритмите за подреждане и търсене ще бъдат други, отчитащи характерните особености на съответната структура.

Блок-схема на алгоритъма:

В тази схема е използван знакът ÷, означаващ деление на цели числа, в резултат на което се получава цяло число, ненадминаващо частното на двете числа. Например 3÷2=1.

Търсене на определен елемент в подреден масив от данни често се налага в практиката. Примери за такава дейност са: търсене на картонче в библиотечен каталог, търсене на име в списък, подреден по азбучен ред; търсене на фактура в архив, нареден по датите на издаването, и др.

Задачата за търсене на елемент може да се съпровожда с извличане на някаква допълнителна информация за търсения елемент. В примера с таблицата на студентите може да е необходимо да се узнаят името и успехът на студент със зададен факултетен номер. Най-общо действия от такъв характер се наричат „извличане на справки".

3. Вмъкване на елемент в подреден масив

Даден е масив А с N (N≥2) числени елемента, подредени по големина, и число В. Числото В да стане елемент на масива А така, че да се запази наредбата. Предполагаме, че сред елементите няма еднакви.

Блок-схема на алгоритъма:

4. Премахване на елемент от подреден масив

Даден е масив А с N (N≥2) числени елемента подредени по големина. Дадено е и числото В. Елементът на А, равен по стойност на В, да се премахне от масива А.

Следва блок-схема на алгоритъма.

Най-общо действията, свързани с промени в масиви или таблици, се наричат актуализация, или обновяване. Те са характерни за изменящи се информационни системи.

Задача, която е типична при работа с информационни масиви.

Дадени са два подредени масива А и В съответно с по М и N числени елемента. Да се състави нов масив С който съдържа елементите на А и В и също да е подреден.

Ще предполагаме, че А и В нямат общи елементи. Задачи от този тип се наричат “задачи за сливане”.

Алгоритъм. Изразява се в следното: сравняват се по големина първият елемент на А с първия елемент на В. По-малкият от двата се записва като първи елемент на масива С. Следващото сравнение става отново над първите елементи, като считаме, че записаният елемент в С вече отсъства от съответния масив. Така се продължава, докато се изчерпи единият масив. Останалите елементи или елемент на другия масив се дописват в края на масива С. Блок-схема на алгоритъма:

предишна страница

изтегли PDF