Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Массивті ретті түрде қарау
Sequentially looking in an array
Компьютерлік ғылымда сызықтық іздеу немесе реттік іздеу – тізімдегі элементті табу әдісі. Ол тізімдегі әрбір элементті сәйкестік табылғанға дейін немесе тізімнің соңына дейін ретті түрде тексереді. Сызықтық іздеу ең жаман жағдайда сызықтық уақытта жұмыс істейді және ең көп дегенде n салыстыру жасайды, мұнда n – тізімнің ұзындығы. Егер әрбір элементтің ізделу ықтималдығы бірдей болса, сызықтық іздеудің орташа жағдайы n/2 салыстыруды құрайды, бірақ әрбір элемент үшін іздеу ықтималдығы өзгеретін болса, орташа жағдай өзгеруі мүмкін. Сызықтық іздеу көбінесе тиімді болмайды, себебі басқа іздеу алгоритмдері мен тәсілдері, мысалы, екілік іздеу алгоритмі және хэш-кестелер, қысқа тізімдерден басқа барлық жағдайларда іздеуді едәуір жылдамдатуға мүмкіндік береді.
In computer science, linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in linear time in the worst case, and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.
Алгоритм
Сызықтық іздеу тізімдегі әрбір элементті нысаналық мәнмен сәйкес келетін элементті тапқанға дейін тізбектеп тексереді. Егер алгоритм тізімнің соңына жетсе, іздеу сәтсіздікке ұшырайды.
A linear search sequentially checks each element of the list until it finds an element that matches the target value. If the algorithm reaches the end of the list, the search terminates unsuccessfully.
Қолдану
Сызықтық іздеуді іске асыру әдетте өте оңай, және тізімде аз ғана элемент болғанда немесе ретсіз тізімде бір рет іздеу жасағанда тиімді. Егер бір тізімде көптеген мәндерді іздеу қажет болса, жылдам әдіс қолдану үшін тізімді алдын ала өңдеу пайдалы болуы мүмкін. Мысалы, тізімді сұрыптап, екілік іздеуді қолдануға немесе одан тиімді іздеу дерек құрылымын құруға болады. Тізімнің мазмұны жиі өзгеріп тұрса, оны қайта-қайта ұйымдастырудың қиындығы көбірек болуы мүмкін. Сондықтан, теориялық тұрғыдан басқа іздеу алгоритмдері (мысалы, екілік іздеу) сызықтық іздеуден жылдам болғанымен, практикада орташа көлемдегі массивтерде (шамамен 100 элементке дейін) басқа әдіс қолдану тиімсіз болуы мүмкін. Ал үлкен массивтерде, деректер жеткілікті көлемде болса ғана, басқа, жылдам іздеу әдістерін қолданудың мәні бар, себебі деректерді дайындауға (сұрыптауға) кеткен алғашқы уақыт көптеген сызықтық іздеулерге тең болуы мүмкін.
Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an un ordered list. When many values have to be searched in the same list, it often pays to pre process the list in order to use a faster method. For example, one may sort the list and use binary search, or build an efficient search data structure from it. Should the content of the list change frequently, repeated re organization may be more trouble than it is worth. As a result, even though in theory other search algorithms may be faster than linear search (for instance binary search), in practice even on medium sized arrays (around 100 items or less) it might be infeasible to use anything else. On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches.