Data Structure and Algorithms Linear Searching
Linear
search is a very simple search algorithm. In this type of
search, a
sequential search is made over all items one by one. Every
item is
checked and if a match is found then that particular item is
returned, otherwise the search continues till the end of the data
collection.
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 .
Basic Algorithm:
Linear Searching
1st
way :
LINEAR(DATA,
N, ITEM,LOC)
Step
1. Set DATA[N+1] =ITEM
Step
2. Set LOC=1
Step
3. [Search ITEM]
Repeat
while DATA[LOC] != ITEM
Set
LOC=LOC+1
Step
4. if LOC=N+1, then Set LOC=0
Step
5. Exit.
2nd way:
input
: L is List and x is item
output
: i is list index, where item is found. Item is not
found then i = -1
Step
1. n is list element.
Step
2. i increment 0-(n-1) and every value of i goto step 3.
Step
3. L[i] = x ? if true then return i.
Step
4. i = -1.
3rd way:
Step
1. Element n list of L
Step
2. i=0
Step
3. i
Step
4. L[i] = x? If true then goto Step 5
Step
5. return i
Step
6. increment I value and goto step 3
Step
7. i=-1
Step 8. Exit .
Code in C:
#include
void
main()
{
int
list[] = {4,8,2,7,1};
int
i, n = 5;
for(i
= 0; i
if(list[i]
== 7){
printf("We
found 7 in the list at: %d th position\n", i+1 );
}
}
return;
}