LINEAR SEARCH

​

By

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

_{PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY}

• Problem: Given an element x and a set of numerical data that is randomly ordered, find whether or not x is present in the set.
• Algorithm development: The problem of searching an unordered list occurs may not frequently in computing.
• In computer science,  A 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.
• It is widely used to search an element from the unordered list, i.e., the list in which items are not sorted. The worst-case time complexity of linear search is O(n).

Dept of CSE

2025- 26

LINEAR SEARCH

PVPSIT (Autonomous)

Problem Solving Techniques

• Now, let's see the working of the linear search Algorithm.

​

​

• Let the element to be searched is Key = 41.
• Now, start from the first element and compare Key with each element of the array.

​

​

• The value of Key, i.e., 41, is not matched with the first element of the array. So, move to the next element.
• And follow the same process until the respective element is found. �

Dept of CSE

2025- 26

PVPSIT (Autonomous)

Problem Solving Techniques

​

​

​

​

​

​

​

​

• Now, the element to be searched is found. So algorithm will return the index of the element matched.

​

Dept of CSE

2025- 26

PVPSIT (Autonomous)

Problem Solving Techniques

• Linear Search complexity
• Time Complexity

​

​

​

​

• Best Case Complexity - In Linear search, best case occurs when the element we are finding is at the first position of the array. The best-case time complexity of linear search is O(1).
• Average Case Complexity - The average case time complexity of linear search is O(n).
• Worst Case Complexity - In Linear search, the worst case occurs when the element we are looking is present at the end of the array. The worst-case in linear search could be when the target element is not present in the given array, and we have to traverse the entire array. The worst-case time complexity of linear search is O(n).

​

​

Dept of CSE

2025- 26

PVPSIT (Autonomous)

Problem Solving Techniques

• Space Complexity

​

Dept of CSE

2025- 26

PVPSIT (Autonomous)

Problem Solving Techniques

1. Establish the array a[1..n], and the value sought x.
2. Assign the pos to -1 and i to 1.
3. While all the elements have not been examined repeatedly do

a. if the value sought is equal to current array value then

(a.1) Assign i to pos and return pos

a’. increment i value by 1

4. If the pos is equal to -1 then write out Value not found

else write out value found at pos

Dept of CSE

2025- 26

Algorithm Description

PVPSIT (Autonomous)

Problem Solving Techniques

• Assume an Array a[1..n] is already Established.
• Step 0: Start 
• Step 1: Read Key
• Step 1: set pos = -1  
• Step 2: set i = 1  
• Step 3: Repeat step 3.1 and 3.2 till i <= n  
• Step 3.1: if a[i] == Key then set pos = i go to step 4  
• Step 3.2: set i = i + 1  
• Step 4: if pos = -1  then print "value is not present in the array " 

Otherwise print “Value is present at ith index”

• Step 5: Stop  

​

Dept of CSE

2025- 26

Algorithm

PVPSIT (Autonomous)

Problem Solving Techniques

• begin

A[1..n] = [70, 40, 30, 11, 57, 41, 25, 14, 52]

key := 41

pos = -1

for i = 1 to n do

If a[i] = key then

begin

pos = i

return pos

end

If pos = -1 then display “Element is not found” else

Display “Element is found at pos”

• end

Dept of CSE

2025- 26

Pseudo-code

PVPSIT (Autonomous)

Problem Solving Techniques

Dept of CSE

2025- 26

PVPSIT (Autonomous)

Problem Solving Techniques

• Applications: 
• Linear search can be applied to both single-dimensional and multi-dimensional arrays.

Dept of CSE

2025- 26

PVPSIT (Autonomous)

Problem Solving Techniques