Linear Search

SEARCH ALGORITHM

In cs,a search algorithm is an algorithm that retrieves information stored within some data structure

Data structures can include linked list,arrays,search trees ,hash tables or various other storage method

TWO SEARCH ALGORITHM
1.LINEAR SEARCH
Linear search or sequential search is a method for finding target value within a list

How it works?
a. It sequentially checks each element of the list for the target value until a match is found or until all elements have been searched
b. It works on both sorted and unsorted data

Problem Statement:
Given a list of n Elements with the values or records Lo…..Ln-1,and target value T, the following subroutine uses linear search to find the indexof the target T in L .

Basic Algorithm:
Set i to 0
If Li=T ,The search terminates successfully; return i
else
increase i by 1
i<n ,goto step2 . otherwise ,the search terminates unsuccessfully.

IMPLEMENTATION OF LINEAR SEARCH ALGORITHM IN ARRAYS

int linearsearch(int *arr,int size,int target)
{
for(int index=0;index< size; index++)
if(arr[index]==target)
return index;
return -1:
}

arr= 7 5 9 210 (size=5,target=2)

Time complexity of linear search in arrays:

approach1:
Best case: number of iterations=1 (we will able to find target or required element in one search ,and it is possible when the elements we are searching for is present at start of array)

Worst case: number of iteration = n+1 ( we will not be able to find element at all in array ,so we go on searching entire array so no of iteratuion is n+1 ,why n+1?
n times we searched all the elements and + 1 times to come out from loop

average :number of iterations = (n+2)/2
time complexity=O(n)

Approach 2:

Recurrence relation:

T(n)=T(n-1)+1 if n>1
(if n is total size of the problem ,so by just one comparison you can decrease the size of problem by 1,incase if it is not the target element then we can say that
target element may be prsent in remaing element (n-1) element

T(1)=1 if n=1

so ,we can say T(n)=O(n)