Definition of Linear Search
Linear search is a straightforward searching algorithm that traverses a given list or array of elements sequentially to find a specific target element. It starts from the beginning and checks each element until a match is found or the entire list is traversed.
The linear search algorithm was introduced by Richard E. Bellman in 1963. Bellman is the same scientist who created the Bellman Ford algorithm.
–
Algorithm of Linear Search
- Start at the beginning of the list.
- Compare the target element with the current element.
- If they match, the search is successful, and the element is found.
- If the elements do not match, move to the next element in the list.
- Repeat steps 2-4 until the target element is found or the end of the list is reached.
Working of linear search
Let’s consider an example to better understand linear search. Suppose we have an array of integers: [5, 8, 3, 10, 1, 12, 7, 4].
We want to find the element 12 using linear search.
–
Start at the beginning of the array: [5, 8, 3, 10, 1, 12, 7, 4].
- Compare the first element, 5, with the target element, 12.
They don’t match.
–
- Move to the next element, 8.
They still don’t match.
–
- Continue comparing with each subsequent element until we reach 12, which is a match.
They still don’t match.
–
They still don’t match.
–
They still don’t match.
–
The search is successful, and the element 12 is found and the index of 12 is 6.
Source Code for Linear Searching
// COMPUTER GEEK – compgeek.co.in
// Write a program for Linear Search
#include <stdio.h>
//Linear Search Starts
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Element found, return the index
}
}
return -1; // Element not found
}
int main() {
int size;
printf(“Enter the size of the array: “);
scanf(“%d”, &size);
int arr[size];
printf(“Enter %d elements in the array:\n”, size);
//Filling the elements of array
for (int i = 0; i < size; i++) {
scanf(“%d”, &arr[i]);
}
//Target number you searched for
int target;
printf(“Enter the element to search for: “);
scanf(“%d”, &target);
int result = linearSearch(arr, size, target);
if (result == -1) {
printf(“Element not found in the array.\n”);
} else {
printf(“Element found at index: %d\n”, result);
}
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Linear Search
#include <iostream>
// Linear Search Function
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Element found, return the index
}
}
return -1; // Element not found
}
int main() {
int size;
std::cout << “Enter the size of the array: “;
std::cin >> size;
int arr[size];
std::cout << “Enter ” << size << ” elements in the array:\n”;
// Filling the elements of the array
for (int i = 0; i < size; i++) {
std::cin >> arr[i];
}
// Target number you searched for
int target;
std::cout << “Enter the element to search for: “;
std::cin >> target;
int result = linearSearch(arr, size, target);
if (result == -1) {
std::cout << “Element not found in the array.\n”;
} else {
std::cout << “Element found at index: ” << result << std::endl;
}
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Linear Search
import java.util.Scanner;
public class LinearSearch {
// Linear Search Function
public static int linearSearch(int[] arr, int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Element found, return the index
}
}
return -1; // Element not found
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“Enter the size of the array: “);
int size = scanner.nextInt();
int[] arr = new int[size];
System.out.println(“Enter ” + size + ” elements in the array:”);
// Filling the elements of the array
for (int i = 0; i < size; i++) {
arr[i] = scanner.nextInt();
}
// Target number you searched for
System.out.print(“Enter the element to search for: “);
int target = scanner.nextInt();
int result = linearSearch(arr, size, target);
if (result == -1) {
System.out.println(“Element not found in the array.”);
} else {
System.out.println(“Element found at index: ” + result);
}
scanner.close();
}
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Linear Search
# Linear Search Function
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Element found, return the index
return -1 # Element not found
def main():
size = int(input(“Enter the size of the array: “))
arr = []
print(“Enter”, size, “elements in the array:”)
# Filling the elements of the array
for _ in range(size):
arr.append(int(input()))
# Target number you searched for
target = int(input(“Enter the element to search for: “))
result = linear_search(arr, target)
if result == -1:
print(“Element not found in the array.”)
else:
print(“Element found at index:”, result)
if __name__ == “__main__”:
main()
Time Complexity
The time complexity of linear search is directly proportional to the size of the list or array.
- In the worst-case, when the target element is located at the end of the list or not present at all, linear search would iterate through all the elements, resulting in a time complexity of O(n), where n is the number of elements in the list.
- In the best-case, the target element is present in the array[1], resulting in a time complexity of O(1).
- In the average case, when the target element is present in the list, but its exact position is unknown. In this scenario, the algorithm will traverse, on average, half of the elements in the collection before finding the target element.
In this case,
Average case = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)/8 = int(36/8) = 4, which is equal to n/2.
Mathematically, if we assume that there are n elements in the list, the average case time complexity of linear search can be expressed as O(n/2) or simply O(n), as we drop the constant factor.
.
Advantages of linear search
- Simple and easy to implement.
- Works well for small lists.
- No requirement for a sorted list.
- Requires minimal additional memory.
Disadvantages of linear search
- Inefficient for large datasets.
- Time complexity of O(n) in worst case & average case.
- May need to search through the entire list.
- Lack of efficiency compared to other search algorithms.
- Not suitable for real-time or time-critical applications.
Applications of linear search
- Finding an element
Whether the list is sorted or unsorted, linear search can locate the desired element by sequentially scanning through the elements until a match is found.
.
- Finding the maximum or minimum element
Linear search can be used to determine the maximum or minimum value within a list. By iterating through the elements and comparing them with the current maximum or minimum, you can update the values accordingly. This is done in selection sort also.
.
- Counting occurrences
By iterating through the list and incrementing a counter whenever a match is found, you can determine the frequency of the desired element.
.
- Index retrieval
By iterating through the list and comparing elements until a match is found, you can determine the index position of the desired element.
Test Yourself
Q1- Explain the working of the linear search algorithm.
The linear search algorithm sequentially checks each element in a list or array to find a specific target element. It starts from the beginning and compares the target element with each element in the list until a match is found or the end of the list is reached.
Q2- What is the time complexity of linear search in the worst-case scenario?
The worst-case time complexity of linear search is O(n), where n is the number of elements in the list. This occurs when the target element is located at the end of the list or not present at all, requiring iteration through all the elements.
Q3- How does the size of the input data affect the performance of linear search?
The performance of linear search is directly affected by the size of the input data. As the size of the input data increases, the performance of linear search tends to degrade. This is primarily because linear search involves sequentially scanning through each element in the data until the target element is found or the entire dataset is searched.
Q4- When might you choose to use linear search over other search algorithms? Provide real-world scenarios where linear search would be a suitable choice.
Linear search may not be the most efficient search algorithm in many cases, but there are situations where it can still be a suitable choice, especially when considering simplicity, ease of implementation, and specific use cases. Here are some real-world scenarios
- Small Datasets – When dealing with very small datasets, the overhead of implementing more complex search algorithms like binary search may not be justified. Linear search can be simpler to implement and understand in such cases.
- Unordered Data – If the data is unsorted, linear search is a straightforward choice since other search algorithms like binary search require sorted data to work efficiently.
- Early Match Importance – In scenarios where you need to find the first occurrence of a target element, linear search can be effective. You can stop the search as soon as you find the first match, potentially saving time compared to other algorithms.
- Search on Small Portion of Data – If you only need to search a small portion of a larger dataset, linear search might be reasonable, especially if the cost of preprocessing the data for other algorithms is higher than the savings in search time.
Q5- What is the time complexity of linear search in the average case?
O(1)
O(log n)
O(n)
O(n2)
Ans – (3)
Q6- Linear search is most suitable for which of the following scenarios?
Large sorted datasets
Real-time applications
Small unsorted lists
Time-critical applications
Ans – (3)
Q7-
What is the worst-case time complexity of linear search?
O(1)
O(log n)
O(n^2)
O(n)
Ans – (4)
Q8- Which search algorithm is more efficient than linear search for large datasets?
Bubble sort
Binary search
Quick sort
Insertion sort
Ans – (2)
Explanation – Binary search has a time complexity of O(log n), where n is the number of elements in the dataset. This logarithmic time complexity makes binary search highly efficient, especially for larger datasets, as it quickly reduces the search space by half with each comparison.
Q9- Which type of list is required for linear search?
Only a sorted list
Only an unsorted list
Both sorted and unsorted lists
None of the above
Ans – (3)
Q10- Which of the following algorithms is based on linear search?
Bubble sort
Insertion sort
Binary search
Quick sort
Ans – (2)
Explanation – Insertion sort is an algorithm that involves iterating through a list of elements and repeatedly inserting each element into its correct position within a sorted sublist. The process of finding the correct position for insertion involves comparisons, similar to a linear search. However, unlike a traditional linear search, insertion sort is used for sorting the entire list rather than searching for a specific element.
