Linear Search
- Searching is the process of finding a particular value or key value in a set of values.
- There are two types of searching:
- Linear Search
- Binary Search
- Linear Search is a sequential search algorithm that searches for the key value linearly from one end to the other end of the list.
- The searching process starts at the first place and traverses all the elements one after another until the key is found. Otherwise, the searching process continues until the last element.
- Algorithm outcomes – Two results:
- Search key present
- Search key not present
Video Lecture
Linear Search Operation
Algorithm
LinearSearch(A[0]..A[n-1], K)
Input: Array A contains n elements and Search Key K.
Output: If search key K is present, return the index; if not present, return -1.
Step 1: Start.
Step 2: Input array A and Search Key K.
Step 3: For i = 0 to n-1
Step 4: If A[i] == K, then output the index i and go to Step 7.
Step 5: Else, go to Step 3.
Step 6: Output -1.
Step 7: Stop.
Working of Linear Search Algorithm - Example
Linear Search Code
#include <stdio.h>
int LinearSearch(int A[], int n, int key)
{
for (int i = 0; i < n; i++)
if (A[i] == key)
return i;
return -1;
}
void InputArray(int A[], int n)
{
int i;
printf("Enter the %d Elements\n",n);
for (i = 0; i < n; i++)
{
scanf("%d",&A[i]);
}
}
int main(void)
{
int A[100],n, key,i;
printf("Enter the size of the array \n");
scanf("%d",&n);
InputArray(A,n);
printf("\n Enter Search key value\n");
scanf("%d",&key);
// Function call to input array
int result = LinearSearch(A, n, key);
if(result == -1)
printf("Element is not present in array");
else
printf("Element is present at index %d", result);
return 0;
}
#include
using namespace std;
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Target found, return the index
}
}
return -1; // Target not found
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 3;
int result = linearSearch(arr, size, target);
if (result != -1) {
cout << "Element found at index: " << result << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Target found, return the index
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int target = 3;
int result = linearSearch(arr, target);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found");
}
}
}
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index # Target found, return the index
return -1 # Target not found
# Example usage
arr = [1, 2, 3, 4, 5]
target = 3
result = linear_search(arr, target)
if result != -1:
print(f"Element found at index: {result}")
else:
print("Element not found")
Analysis of Linear Search
Time Complexity
The algorithm's basic operation is comparison. The basic operation comparison decides the time complexity of the linear search algorithm. Time complexity of the linear search algorithm is based on how many times the comparison operation is performed.
Best Case: If the search key is present in A[0], the linear search algorithm performs only one comparison. Thus, Best(n) = 1, Best(n) = O(1); the order of growth is constant.
Worst Case: If the search key is present in A[n-1] or not present at all, the linear search algorithm performs a maximum of n comparisons. Thus, Worst(n) = n, Worst(n) = O(n); the order of growth is linear. The average case complexity of linear search is O(n).
Space Complexity
The linear search algorithm requires memory for the array A and the search key. No extra memory is required. The space complexity of linear search is O(1).
Comparison of Insertion Sort and Bubble Sort
