§ 12. Пошук элементаў з зададзенымі ўласцівасцямі

12.1. Лінейны пошук

Разгледзім, як ажыццяўляецца пошук даных, якія захоўваюцца ў масіве.

Сярод разнавіднасцей самых простых задач пошуку, якія сустракаюцца на практыцы, можна вылучыць наступныя тыпы:

1. Знайсці хоць бы адзін элемент, роўны зададзенаму элементу x. У выніку атрымліваюць i — індэкс (нумар) элемента масіву, такі, што a[i] = x.
2. Знайсці ўсе элементы, роўныя зададзенаму x. У выніку атрымліваюць колькасць такіх элементаў і (ці) іх індэксы.

Часам пошук арганізуецца не па супадзенні з элементам x, а па выкананні некаторых умоў. Прыкладам можа служыць пошук элементаў, якія задавальняюць умову: x1 ≤ a[i] ≤ x2, дзе x1 і x2 зададзены.

Калі няма ніякай дадатковай  інфармацыі пра даныя, якія адшукваюцца, то самы просты падыход — паслядоўны прагляд элементаў масіву.

Алгарытм, пры якім для пошуку патрэбнага элемента праглядаюць усе элементы масіву, называецца лінейным або паслядоўным пошукам.

Чалавек увесь час сутыкаецца з задачамі пошуку патрэбнай інфармацыі. У сучасным свеце інфармацыю шукаюць з выкарыстаннем сеткі Інтэрнэт. Таксама прыкладам пошуку інфармацыі можа служыць праца з даведнікамі ці бібліятэчнай картатэкай, якія могуць быць электроннымі. 

Для таго каб гэты пошук быў выніковым і хуткім, распрацоўваюць эфектыўныя алгарытмы пошуку. Важную ролю ў працэсе пошуку інфармацыі адыгрывае спосаб захоўвання даных. Адной з самых простых структур для гэтага з’яўляецца масіў.

Алгарытмы пошуку можна падзяліць на алгарытмы, якія выкарыстоўваюць неўпарадкаваныя наборы даных, і на алгарытмы, што працуюць з папярэдне ўпарадкаваным наборам даных.

Прыкладам пошуку ў неўпарадкаваным наборы даных можа служыць пошук сшытка пэўнага навучэнца ў стосе сшыткаў, здадзеных навучэнцамі на праверку. Каб знайсці патрэбны сшытак, магчыма, прыйдзецца перагледзець усе. Пошук у слоўніку — пошук ва ўпарадкаваным наборы даных, г. зн. усе словы размешчаны ў алфавітным парадку.