(Theory in English)
Linear Search is a searching algorithm used to find an element in a collection (array).
It is also called Sequential Search because it checks each element one by one until the desired value is found.
🔹 How Linear Search Works?
- Start from the first element and compare it with the key (the value to be searched).
- If the key is found, return the index of that element.
- If the key is not found, continue checking until the last element.
- If the key is not in the array, return -1 (indicating the element is not present).
🔹 Time Complexity of Linear Search
✅ Best Case (O(1)) → When the key is at the first position.
✅ Worst Case (O(n)) → When the key is not present or at the last position.
✅ Average Case (O(n)) → When the key is somewhere in the middle.
📌 Linear Search in C (Dynamic Memory Allocation)
#include <stdio.h>
#include <stdlib.h> // For malloc() and free()
// Function for Linear Search
int linearSearch(int *arr, int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}
int main() {
int n, key, result;
// Get array size from user
printf("Enter the number of elements: ");
scanf("%d", &n);
// Dynamic Memory Allocation for array
int *arr = (int *)malloc(n * sizeof(int));
// Checking if memory allocation is successful
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
// Getting array elements from user
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Get the key to search
printf("Enter the element to search: ");
scanf("%d", &key);
// Call linearSearch function
result = linearSearch(arr, n, key);
// Print the result
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found!\n");
}
// Free allocated memory
free(arr);
return 0;
}
📌 Line-by-Line Explanation (English)
1️⃣ Header Files
#include <stdio.h>
#include <stdlib.h> // For malloc() and free()
✅ stdio.h → Used for input-output functions (printf, scanf).
✅ stdlib.h → Used for dynamic memory allocation (malloc, free).
2️⃣ Function for Linear Search
int linearSearch(int *arr, int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}
📌 linearSearch function takes a pointer arr, the size of the array, and the key to search as inputs.
📌 It loops through each element and compares it with the key.
📌 If found, it returns the index of the key.
📌 If not found, it returns -1.
3️⃣ Taking Input from the User
printf("Enter the number of elements: ");
scanf("%d", &n);
📌 User enters the size of the array (n).
4️⃣ Allocating Memory Dynamically
int *arr = (int *)malloc(n * sizeof(int));
📌 malloc(n * sizeof(int)) → Allocates memory for n integers dynamically.
📌 arr is a pointer that stores the address of allocated memory.
5️⃣ Checking if Memory Allocation was Successful
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
📌 If malloc fails to allocate memory, arr will be NULL.
📌 If allocation fails, an error message is displayed, and the program exits.
6️⃣ Taking Array Elements from the User
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
📌 A for loop is used to take n elements as input from the user.
7️⃣ Taking the Key to Search from the User
printf("Enter the element to search: ");
scanf("%d", &key);
📌 User enters the key (the value to search for).
8️⃣ Calling the Linear Search Function
result = linearSearch(arr, n, key);
📌 Calls the linearSearch() function and stores the returned value in result.
9️⃣ Checking the Search Result
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found!\n");
}
📌 If result != -1, it means the element is found, and the index is printed.
📌 If result == -1, it means the element is not found, and an appropriate message is displayed.
🔟 Freeing the Allocated Memory
free(arr);
📌 Since we allocated memory dynamically using malloc(), we must free it after use to avoid memory leaks.
📌 Example Output
Enter the number of elements: 5
Enter 5 elements: 10 20 30 40 50
Enter the element to search: 30
Element found at index 2
📌 Key Takeaways
✅ Linear Search is a simple searching algorithm that checks elements sequentially.
✅ Time Complexity → Worst case O(n), Best case O(1).
✅ Dynamic Memory Allocation → malloc() is used to allocate memory dynamically.
✅ Memory Management → free(arr) is used to release allocated memory.
📌 When to Use Linear Search?
🔹 When the size of the array is small.
🔹 When data is unsorted.
🔹 When you need dynamic memory allocation.
0 Comments