§ 12. Пошук элементаў з зададзенымі ўласцівасцямі
12.1. Лінейны пошук
Разгледзім, як ажыццяўляецца пошук даных, якія захоўваюцца ў масіве. Сярод разнавіднасцей самых простых задач пошуку, якія сустракаюцца на практыцы, можна вылучыць наступныя тыпы: 1. Знайсці хоць бы адзін элемент, роўны зададзенаму элементу x. У выніку атрымліваюць i — індэкс (нумар) элемента масіву, такі, што a[i] = x. Часам пошук арганізуецца не па супадзенні з элементам x, а па выкананні некаторых умоў. Прыкладам можа служыць пошук элементаў, якія задавальняюць умову: x1 ≤ a[i] ≤ x2, дзе x1 і x2 зададзены. Калі няма ніякай дадатковай інфармацыі пра даныя, якія адшукваюцца, то самы просты падыход — паслядоўны прагляд элементаў масіву. Алгарытм, пры якім для пошуку патрэбнага элемента праглядаюць усе элементы масіву, называецца лінейным або паслядоўным пошукам. |
Чалавек увесь час сутыкаецца з задачамі пошуку патрэбнай інфармацыі. У сучасным свеце інфармацыю шукаюць з выкарыстаннем сеткі Інтэрнэт. Таксама прыкладам пошуку інфармацыі можа служыць праца з даведнікамі ці бібліятэчнай картатэкай, якія могуць быць электроннымі. Для таго каб гэты пошук быў выніковым і хуткім, распрацоўваюць эфектыўныя алгарытмы пошуку. Важную ролю ў працэсе пошуку інфармацыі адыгрывае спосаб захоўвання даных. Адной з самых простых структур для гэтага з’яўляецца масіў. Алгарытмы пошуку можна падзяліць на алгарытмы, якія выкарыстоўваюць неўпарадкаваныя наборы даных, і на алгарытмы, што працуюць з папярэдне ўпарадкаваным наборам даных. Прыкладам пошуку ў неўпарадкаваным наборы даных можа служыць пошук сшытка пэўнага навучэнца ў стосе сшыткаў, здадзеных навучэнцамі на праверку. Каб знайсці патрэбны сшытак, магчыма, прыйдзецца перагледзець усе. Пошук у слоўніку — пошук ва ўпарадкаваным наборы даных, г. зн. усе словы размешчаны ў алфавітным парадку. |