Linear Search
Linear search, also known as sequential search, is a simple searching algorithm that searches for a target element in a list or array one element at a time, starting from the beginning and moving sequentially through the list until the element is found or the end of the list is reached. Here's a detailed algorithm for linear search, along with a real-time example:
1.Linear Search Algorithm:Start from the first element (index 0) of the list.
2.Compare the current element with the target element you are searching for.
3.If the current element is equal to the target element, you have found a match, and you can return the index of the current element as the result.
4.If the current element is not equal to the target element and you have not reached the end of the list, move to the next element (increment the index by 1) and repeat steps 2-3.
5.If you have reached the end of the list (i.e., you have compared all elements) and have not found a match, return a "not found" or "element not in the list" indicator.
Real-Time Example:
Let's say you have an array of integers and you want to search for the number 7 in this array using linear search.
Array: [12, 34, 5, 2, 7, 8, 19, 42]
1.Let's implement the linear search algorithm step by step:Start at index 0, which is the first element: 12.
2.Compare 12 with the target element (7). They are not equal.
3.Move to the next element at index 1: 34.
4.Compare 34 with 7. They are not equal.
5.Continue this process until you reach index 4, where the element is 7. You have found a match!
6.Return the index 4 as the result.
In this example, linear search successfully found the target element (7) at index 4. If the target element was not in the list, you would continue searching until you reach the end of the list and return a "not found" indicator.
Pseudo code
function linear_search(array, target):
for each element in array:
if element equals target:
return index of element
return -1 // Target not found in the array
In this pseudocode:
array represents the list or array in which you want to search.
target represents the element you are looking for.
The for each element in array loop iterates through each element of the array.
Inside the loop, it checks if the current element is equal to the target.
If a match is found, it returns the index of the element.
If the loop completes without finding a match, it returns -1 to indicate that the target element is not in the array.
Time Complexity: The time complexity of the linear search algorithm is O(n), where "n" is the number of elements in the array. This is because, in the worst case, you may have to traverse the entire array to find the target element. In the best-case scenario, where the target element is found at the beginning of the array, the time complexity is O(1), but we typically consider the worst-case time complexity.
The space complexity of the linear search algorithm is O(1), which means it uses a constant amount of additional memory regardless of the size of the input array. This is because the algorithm does not require any additional data structures or memory allocation that depend on the size of the input.
In summary:
Time Complexity: O(n) in the worst case, O(1) in the best case.
Space Complexity: O(1).
Space Complexity: O(1).
C program - Linear Search
/*******************************************************************************/
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Return the index of the target element if found
}
}
return -1; // Return -1 if the target element is not found
}
int main()
{
int arr[100];
int n, i, target, result;
/*
* Read size of array and elements in array
*/
printf("Enter size of array :: ");
scanf("%d", &n);
printf("\nEnter elements in array: \n");
for(i=0; i<n; i++)
{
printf("Enter %d element in array :: ",i+1);
scanf("%d", &arr[i]);
}
printf("\nEnter the element to search within the array: ");
scanf("%d", &target);
/* call the linear search function */
result = linearSearch(arr, n, target);
if (result != -1) {
printf("Element %d found at index %d.\n", target, result);
} else {
printf("Element %d not found in the list.\n", target);
}
return 0;
}
Comments
Post a Comment