Екілік іздеу және сызықтық іздеу
Сызықтық іздеу, сондай-ақ тізбекті іздеу деп те белгілі - ең қарапайым іздеу алгоритмі. Ол тізімдегі әрбір элементті тексеру арқылы тізімдегі көрсетілген мәнді іздейді. Екілік іздеу де сұрыпталған тізімде көрсетілген мәнді табу үшін қолданылатын әдіс болып табылады. Екілік іздеу әдісі тексерілген элементтердің санын (әр итерацияда) екі есе азайтады, бұл тізімде берілген элементті табуға кететін уақытты азайтады.
Сызықтық іздеу дегеніміз не?
Сызықтық іздеу - тізімдегі әрбір элементті көрсетілген элементті тапқанша ретімен тексеретін ең қарапайым іздеу әдісі. Сызықтық іздеу әдісінің кірісі реттілік (массив, жинақ немесе жол сияқты) және іздеуді қажет ететін элемент болып табылады. Көрсетілген элемент берілген реттілік ішінде болса шығыс ақиқат немесе ол реттілікте болмаса жалған болады. Бұл әдіс көрсетілген элемент табылмайынша тізімдегі әрбір элементті тексеретіндіктен, ең нашар жағдайда ол қажетті элементті тапқанға дейін тізімдегі барлық элементтерден өтеді. Сызықтық іздеудің күрделілігі o(n). Сондықтан ол үлкен тізімдердегі элементтерді іздеу кезінде пайдалану үшін тым баяу болып саналады. Бірақ бұл өте қарапайым және орындау оңай.
Екілік іздеу дегеніміз не?
Екілік іздеу сонымен қатар сұрыпталған тізімде көрсетілген элементті табу үшін қолданылатын әдіс. Бұл әдіс ізделетін элементті тізімнің ортасындағы элементтермен салыстыру арқылы басталады. Егер салыстыру екі элементтің тең екенін анықтаса, әдіс тоқтайды және элементтің орнын қайтарады. Егер ізделетін элемент ортаңғы элементтен үлкен болса, ол сұрыпталған тізімнің тек төменгі жартысын пайдаланып әдісті қайта бастайды. Егер ізделетін элемент ортаңғы элементтен аз болса, ол сұрыпталған тізімнің тек жоғарғы жартысын пайдаланып әдісті қайта бастайды. Егер ізделетін элемент тізімде болмаса, әдіс оны көрсететін бірегей мәнді қайтарады. Сондықтан екілік іздеу әдісі салыстыру нәтижесіне байланысты салыстырылған элементтердің санын (әрбір итерацияда) екі есе азайтады. Демек, екілік іздеу логарифмдік уақытта орындалады, нәтижесінде o(log n) жағдайдың орташа өнімділігі болады.
Екілік іздеу мен сызықтық іздеудің айырмашылығы неде?
Сызықтық іздеу де, екілік іздеу де іздеу әдістері болғанымен, олардың бірнеше айырмашылықтары бар. Екілік іздеу сұрыпталған тізімдерде жұмыс істегенде, лайнерлік іздеу сұрыпталмаған тізімдерде де жұмыс істей алады. Тізімді сұрыптау әдетте n log n орташа жағдай күрделілігіне ие. сызықтық іздеу екілік іздеуге қарағанда қарапайым және қарапайым. Бірақ сызықтық іздеу оның o(n) орташа көрсеткішіне байланысты үлкен тізімдермен пайдалану үшін тым баяу. Екінші жағынан, екілік іздеу үлкен тізімдермен қолдануға болатын тиімдірек әдіс болып саналады. Бірақ екілік іздеуді жүзеге асыру өте қиын болуы мүмкін және зерттеу екілік іздеудің дәл кодын жиырма кітаптың бесеуінде ғана табуға болатынын көрсетті.
