Іздеу. Іздеу есептерінің шешілімі. Іздеу: қайтару арқылы теріп алу

Презентация қосу

Іздеу. Іздеу
есептерінің
шешілімі. Іздеу:
қайтару арқылы
теріп алу.
Іздеу  -  берілген мәні бар
элементтердің орнын табу.
Іздеу

Тізбектеліп іздеу

Бинарлық іздеу
Тізбектеліп іздеу. Тізбектеліп іздеудің
мағынасы элементтерді тізбекпен таңдап
алуды және элементтерді кілт мәнімен
салыстырудан тұрады.

Функция парамертлер ретінде массивті,
элементтер санын және кілт мәнін алады.
Сәйкес элементтің индексін қайталайды, егер
іздеу сәтсіз болса,  -1 мәнін береді. Тізбектеліп
іздеу кез келген тізбек үшін қолайлы,
тізбектеліп іздеудің орталық тиімділігі O(n)
тең болады.
Бинарлық іздеу.
Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана
қолданылады. Мысалы элементтер тұратын массив берілсін.
Тізімнің басындағы және соңындағы элементтердің
индекстері мынадай low=0 high=n-1 дейін болады.
Бинарлық іздеудің алгоритмі:
Массивтің ортаңғы элементінің индексін табу:
mid=(low+high)/2.
Орталық элементтің мәнін кілтпен салыстыру «Key». Егер
салыстыру нәтижесінде сәйкестік бар болса, онда mid
индексін кілтті табу үшін қолданамыз. Егер орталық
элемент мәні кілттен кіші болса, онда қарастырылып
отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз.
Егер керісінше үлкен болса, онда сол жақтағы бөлігінде
іздеу жүргіземіз.
Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын
береміз.

Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген
элементі бар табу керек.
Мысал элементтері:  А
0             1               2           3         4            5           6          7           8
-7 3 5 8 12 16 23 33 55

Low=0
High=8
mid=4
33>A(mid)
0            1                2          3          4          5           6          7         8
-7 3 5 8 12 16 23 33 55

mid
Low=5
High=8
mid=6
33>A(mid)
0 1 2 3 4 5 6 7 8

-7 3 5 8 12 16 23 33 55

Low=7
High=8
mid=7
33=A(mid)
Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық
іздеуде 3 салыстыру жүргізіледі.
Екілік іздеу тармақтары программалауда кең таралған. Екілік
іздеу тармақтарының әрбір төбесінің мәні:
1. Оның сол жағындағы бұтақ төбесінің кез келген мәнінен
үлкен немесе тең.
2. Оның оң жақ бұтағының төбесінің кез келгенінің мәнінен
кіші.
Сызықтық құрылғылар үшін тізбектеліп іздеу алгоритмінің
күрделілігі – О(n) –ға тең. Мұндағы n-құрылым элементтер саны.
Ал аяқталатын бинарлық тармақ үшін күрделілігі – О(log2n)-ға
тең.
Мысалға: 10000 элементтен тұратын тізімде тізбектеп іздеуде
салыстырудың максимальды саны 10000-ға тең болады. Ал
аяқталған тармақта іздеу 14 салыстырудан аспас еді.
Екілік іздеу тармағына элементті осу алгоритмі
(тармақты қарау үнемі түбірден басталады):
1. тармаққа қосылатын мән ағымдағы түйін мәніне
салыстырылады.
2. Егер тармаққа қосылтын мән ағымдағы түйін
мәнінен кіші болса, онда келесілер тексеріледі:
а) егер ағымдағы түйінде ұрпақтар жоқ болса, онда
жаңағы мәні бар түйінді сол жақ ұрпақ ретінде
бекітеміз.
б) әйтпесе, (егер ұрпақ болса) тармақтың  сол жақ
бұтағы арқылы бір деңгейге төмендетеміз.
3. Егер тармаққа қосылатын мән ағымдағы түйін
мәнінен үлкен немесе тең болса, келесілер тексеріледі:
а) егер оң жақтағы ағымдағы түйінде ұрпақтар жоқ
болса, онда мәні бар түйінді оң жақ ұрпқ ретінде
бекітеміз.
Екілік іздеу тармағынан элементті алып тастау.
Тармақтан элементті алып тастау алгоритмі тармақтағы
осы элементтің орналасқан орнына тәуелді болады және
келесі төрт жағдайды қамтиды:
1. Мәні х-ке тең болатын элемент жоқ.
2. Мәні х-ке тең болатын элемент терминальды түйін
болып табылады.
3. Мәні х-ке тең болатын элемент бір ғана ұрпақты
болады.
4. Мәні х-ке тең болатын элемент екі ұрпақты болады.

Бір ғана ұрпағы болатын элементті алып тастауда
ешқандай күрделілік жоқ. Мұндай әрекеттер сызықтық
тізімдегі элементті алып тастауға ұқсас болады.
Егер элемент екі ұрпақты болса, онда екі бағытта
бір ғана сілтемемен көрсетуге келмейді. Бұл
жағдайда өшірілетін элементті ауыстыруға тура
келеді. Ауыстыратын элемент үшін оның сол
жақтағы ең оң жақты элемент, ал оң жақтағы сол
жақты элемент таңдап алынады (6 және 8
өшірілетін элементке мәндері жағынан жақын
элементтер).
Назарларыңызға
рахмет!!!!!!

Ұқсас жұмыстар

Әлсіз құрылымдалған деректерді іздеу

Excel программасында мәліметтер қорымен жұмыс жасау

Ақпарат іздеу

Орта мектептегі информатика оқулықтарына талдау

Патенттік зерттеулер

Инновациялық жобаны іске асыру

Medline - медициналық ақпаратты библиографиялық іздестіру

Заманауи технологиялар және олардың мүмкіндіктері

ИНТЕРНЕТ ЖЕЛІСІНДЕ ҒЫЛЫМИ ПЕДАГОГИКАЛЫҚ АҚПАРАТТЫ ІЗДЕУ

Бұлтты деректерді сақтау

Пәндер