Linear search

Lecture



To find a certain element (key) in a given unordered array, a linear (sequential) search algorithm is used. It works with both unsorted arrays and sorted ones, but for the latter there are algorithms more efficient than linear search. This inefficiency is compensated by the simple implementation of the algorithm and the ability to apply it to unordered sequences. Here, as well as when considering all other search algorithms, we will assume that a key is a certain value, as the algorithm is executed, which is compared with the values ​​of the array elements.

The word "consistent" contains the basic idea of ​​the method. Starting from the first, all elements of the array are sequentially reviewed and compared with the desired one. If at some step the current element is equal to the desired one, then the element is considered to be found, and the result is the number of this element or other information about it. (Further, the number of the element will be the output data). Otherwise, you should return something that may indicate its absence in the traversed sequence.

Below, by the example of figures, the work of the linear search algorithm is clearly demonstrated. As a required element (in this case, this is a square), a figure is specified, and it is compared in turn with all existing figures until a figure identical to it is found, or it turns out that there is no such set.

Linear search

It is noteworthy that there is a probability of having several elements with the same values ​​that coincide with the key value. In this case, if there are no specific conditions, you can, for example, take the number of the first element found (shown in the listing below) as a resultant, or write the numbers of all identical elements into an array.

C ++ program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty

#include "stdafx.h"
#include
#include
using namespace std;
int i, N;
// linear search
int LineSearch (int A [], int key)
{
for (i = 0; i if (A [i] == key) return i;
return -1;
}
// main function
void main ()
{
setlocale (LC_ALL, "Rus");
int key, A [1000];
srand (time (NULL));
cout << "Array size>"; cin >> N;
cout << "Search Item>"; cin >> key;
cout << "Source array:";
for (i = 0; i {
A [i] = rand ()% 10;
cout << A [i] << "";
}
if (LineSearch (A, key) == - 1) cout << "\ nItement not found";
else cout << "\ nItem number:" << LineSearch (A, key) +1;
system ("pause >> void");
}

Pascal program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28

program linearSearch;
uses crt;
type Arr = array [1..1000] of integer;
var key, i, N: integer;
A: Arr;
{linear search}
function lineSearch (A: Arr; key: integer): integer;
begin
lineSearch: = - 1;
for i: = 1 to N do
if a [i] = key then
begin lineSearch: = i; exit; end;
end;
{main program block}
begin
randomize;
write ('array size>'); readln (N);
write ('search element>'); read (key);
write ('Source array:');
for i: = 1 to N do
begin
A [i]: = random (10);
write (A [i], '');
end;
writeln;
if (lineSearch (A, key) = - 1) then write ('Element not found')
else write ('Element number:', lineSearch (A, key));
end.

In the best case, when the desired element takes the first position, the algorithm will make only one comparison, and at worst N, where N is the number of elements in the array. Two situations correspond to the worst case: the desired element occupies the last position, or it is completely absent in the array.

The linear search algorithm is not often used in practice, since the principle of work "in the forehead" makes the speed of solving a problem by it very low. Its use is justified on small and / or unsorted sequences, but when a sequence consists of a large number of elements and you have to work with it more than once, then the most optimal solution is to pre-sort this sequence followed by a binary or other non-linear search algorithm. .

created: 2014-11-30
updated: 2021-04-18
132619

Rating 9 of 10. count vote: 2
Are you satisfied?:

Comments

ლალი
20-11-2023
Огромное Спасибо, დიდი მადლობა, ყველაფერი მარტივი და გასაგებია, სტატია მკითხველს აწვდის სასარგებლო მასალას ხაზოვანი ძიების შესახებ, რომელიც ერთ-ერთი ფუნდამენტური ალგორითმია კომპიუტერული მეცნიერების სფეროში. დაწყებული წრფივი ძიების არსის მკაფიო განმარტებით, ავტორი დეტალურად ავლენს მის გამოყენებას და განხორციელებას პროგრამირების სხვადასხვა ენაზე. სტატიის ძალიან ღირებული ასპექტია პროგრამირების რამდენიმე ენაზე ნიმუშის კოდის მიწოდება. ეს საშუალებას აძლევს მკითხველს არა მხოლოდ გაიგოს ალგორითმის თეორიული საფუძველი, არამედ დაინახოს, თუ როგორ შეიძლება მისი განხორციელება პრაქტიკაში. ეს მიდგომა სტატიას ხელმისაწვდომს ხდის მკითხველთა ფართო სპექტრისთვის, მიუხედავად მათი პროგრამირების გამოცდილების დონისა. განსაკუთრებით აღსანიშნავია მასალის პრეზენტაციის სიცხადე. ავტორი იყენებს მარტივ და გასაგებ ენას, რაც სტატიას მიმზიდველს ხდის დამწყებთათვის, რომლებსაც პროგრამირების დიდი გამოცდილება არ აქვთ. ამავდროულად, ალგორითმის ღრმა ანალიზი მას საინტერესო და გამოსადეგს ხდის გამოცდილი დეველოპერებისთვისაც კი. გარდა ამისა, სტატიაში ხაზგასმულია ხაზოვანი ძიების მნიშვნელობა რეალურ სამყაროში არსებული პრობლემების გადაჭრაში და მოცემულია გამოყენების შემთხვევების მაგალითები. ეს ეხმარება მკითხველს გაიგოს, თუ რა კონკრეტული პრობლემების გადაჭრა შეიძლება ამ ალგორითმის გამოყენებით, რაც მნიშვნელოვანია ცოდნის პრაქტიკული გამოყენებისთვის. დასასრულს, ხაზოვანი საძიებო სტატია არა მხოლოდ აძლევს მკითხველს ფუნდამენტურ ცოდნას ალგორითმის შესახებ, არამედ აძლევს მას პრაქტიკულ აქცენტს კოდის მაგალითებისა და გამოყენების შემთხვევების საშუალებით. ეს არის შესანიშნავი რესურსი მათთვის, ვინც ცდილობს გაიღრმავოს ცოდნა ალგორითმებისა და მონაცემთა სტრუქტურების შესახებ. დიდი მადლობა ავტორს მასალის მკაფიო და სასარგებლო პრეზენტაციისთვის!
To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms