Searching for an algorithm is basically considered as an essential stage in computer science that includes using a step-by-step procedure for locating a specific piece of data among a large set of data.
In order to finish the procedure, all search algorithms utilize a search key.
There are different types of search algorithms available in computer science, and how they are employed determines the performance and efficiency of the data provided (the manner in which the data is being used).
These algorithms are divided into two groups based on the type of search operations they perform.
- Sequential Search: This method traverses the list or array consecutively, checking each element. (Same as in the case of a Linear Search.)
- Interval Search: These algorithms were created with the goal of searching sorted data structures. These types of search algorithms are more efficient than Linear Search as they continually target the center of the search structure and divide the search space in half. Example: Binary Search.
Types of Searching Algorithms
- Linear Search
- Binary Search
- Jump Search
- Interpolation Search
- Exponential Search
- Sublist Search (Searching a linked list inside another list)
- Fibonacci Search
- The Ubiquitous Binary Search
Linear Search
A Linear Search, which is also popularly known as a sequential search, is a process for finding an item in a list of items. This sort of searching algorithm checks each element of the list one by one until a match is found or the entire list is searched.
In worst-case scenarios, the Linear Search takes linear time and performs at most n comparisons, where n is the list's length.
If each element has an equal chance of being searched, Linear Search has an average case of n+1/2 comparisons, but the average case can be influenced if the search probability for each element differs. Linear Search is rarely feasible as other search algorithms and schemes (such as the binary search algorithm and hash tables) that provide significantly faster search operation for all lists.
The following are the steps involved in implementing Linear Search:
- We must first use a for loop to traverse the array elements.
- In the process of searching an element in a list of elements, we should start by comparing the search element with the current list of elements in each iteration of the loop, and if the elements match, return the index of the relevant array element.
- If the element we're looking for doesn't match, move on to the next one.
Return -1, if there is no match or the search element is not found in the given array.
What is Linear Search in C Programming?
In C, we perform a Linear Search to see if a number is present in an array. It is also known as sequential search in which we compare each element with the one we're looking for until we find it or when the list runs out.
Algorithm of Linear Search (Approach)
Searching is the method of finding a certain item in a list of items. If the element is found in the list, the process is considered successful, and the location of that element is returned; otherwise, the search is considered unsuccessful.
In Linear Search, the index or search location in the specified array is found. It starts the search by comparing the search key to the array/first list's element. If the first element does not match the search key, the next element will be compared, and so on until the match is discovered or the array ends. If a match is discovered, the index is returned; otherwise, it reaches the end of the array or list, indicating that the search key is not available.
For a better understanding of the Linear search, we are going to see an example.
Example:
Given array = {50, 90, 30, 70, 60};
Assume the search key is 30. Next, scan the array and compare each element to the search key. The array's first element is 50, but 50 is not equal to 30, therefore continue on to the next element. The next element is 90, but it isn't equal to 30, so it's time to move on to the next one. The array's next element is 30, which is the same as the search key 30, thus returning the index of the array's current element.
The above example was the case where the search key was present in the array. Now consider a case where the search key is not present. Let’s assume that the search key is equal to 10. Compare each element in the array with the search element. It fails to match with 50, 90, 30, 70, 60, and eventually reaches the array's conclusion. As a result, return -1 or print element is not present in the array, indicating that the search key is not available.
Implementing C Program for Linear Search
Code for Linear Search in C program is given below:
|
#include <stdio.h> void main() { int num; int i, key, element_found = 0; printf("Enter number of elements you would like to take as input: "); scanf("%d", &num); int arr[num]; printf("\nEnter all the elements of your choice:"); for (i = 0; i < num; i++) { scanf("%d", &arr[i]); } printf("\nEnter the key element that you would like to be searched: "); scanf("%d", &key); /* Linear search starts */ for (i = 0; i < num ; i++) { if (key == arr[i] ) { element_found = 1; break; } } if (element_found == 1) printf("we got the element at index %d",i+1); else printf("we haven’t got element at any index in the array\n"); } |
Output:
Explanation of Code:
- In Linear Search, we look for an element or value in an array by traversing it from the beginning to the end until the required element or value is discovered.
- The array is searched progressively, and if the key element to be searched is found in the array, the position is returned; otherwise, -1 is returned.
- We haven't created a function particularly for Linear Search in this C program; instead, we can check for the presence of an element in an array in the main function.
- We traverse the array starting at the 0th index and increasing in order of index, breaking the loop there and printing the element's position in the array, but if the element requested is not present in the array, we simply display "Element is not present in the array."
- If we had written a separate Linear Search function and the element could not be found in the array, we would have returned -1 or print “Element is not present in array” indicating that the element was not present.
Linear Search for Multiple Occurrences
The code below prints all the locations where the needed element can be found, as well as the number of times it appears in the list of the program.
|
#include <stdio.h> int main() { int arr[100], key, i, no, count = 0, search; printf("Enter number of elements you would like to take as input\n"); scanf("%d", &no); printf("Enter %d numbers\n", no); for (i= 0; i < no; i++) scanf("%d", &arr[i]); printf("Enter a number that you would like to search\n"); scanf("%d", &search); for (i = 0; i < no; i++) { if (arr[i] == search) { printf("%d is present at position %d.\n", search, i+1); count++; } } if (count == 0) printf("%d key is not present in the array.\n", search); else printf("%d is present %d times in the array.\n", search, count); return 0; } |
Output:
Linear Search Using a Function
Code for implementing Linear Search in C program by using function is provided below:
|
#include <stdio.h> int linear_search_function(int a[], int n, int key) { for (long i = 0 ;i < n ; i++ ) { if (a[i] == key) return i; } return -1; } int main() { int arr[100], key, k, n, key_position; printf("Enter number of elements in the array\n"); scanf("%d", &n); printf("Enter %d integer(s)\n", n); for (k= 0; k < n; k++) scanf("%d", &arr[k]); printf("Enter a number you would like to search in the array\n"); scanf("%d", &key); key_position = linear_search_function(arr, n, key); if (key_position == -1) printf("%d isn't present in the array.\n", key); else printf("%d is present at location %d.\n", key, key_position+1); return 0; } |
Output:
Linear Search in C Using Recursion
The recursive function is a function that contains a call to itself. Recursion is a method of defining the recursive function. It allows us to break down a big problem into easily manageable single basic situations. Divide and conquer is also a power and a popular computer programming strategy that is widely used for programming.
|
#include <stdio.h> int linear_search_with_recursion(int arr[], int value, int index, int n) { int position = 0; if(index >= n) { return 0; } else if (arr[index] == value) { position = index + 1; return position; } else { return linear_search_with_recursion(arr, value, index+1, n); } return position; } int main() { int n, value, position, m = 0, arr[100]; printf("Enter the total elements in the array that you would like to take:"); scanf("%d", &n); printf("Enter the elements of the array:\n"); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } printf("Enter the element you would like to search in the array: "); scanf("%d", &value); position = linear_search_with_recursion(arr, value, 0, n); if (position != 0) { printf("Element found at position %d ", position); } else { printf("Element not found in the array"); } return 0; } |
Output:
Explanation of Code:
- In Linear Search, we look for an element or value in an array by traversing it from the beginning until the element or value we want is discovered.
- The array is searched progressively, and if the key element to be searched is found in the array, the position is returned; otherwise, "Element not found in the array" is printed.
- In this C program, we've written a recursive function called linear_search_with_recursion() that takes four input arguments and returns the position of an element in an array that the user is searching.
- If the first element is found, the index is returned immediately.
- If it is not the first member of the array, we reduce the size of the array by 1 by removing the first element, which means the array size will be reduced by 1 when Linear Search-with_recursion() is called a second time (n-1). This will continue until the element has been discovered.
Time Complexity of Linear Search in C Program
The time complexity of an algorithm is nothing but the amount of time it takes to run as an algorthm for the whole input. The number of operations to be performed by the algorithm is indicated by the length of input. In this case, it would not consider the algorithm's overall execution time. Instead, when the number of operations in an algorithm increases or decreases, it will provide data on the variation (increase or reduction) in execution time.
Let's look at the complexity of Linear Search in the best, average, and worst-case scenarios.
Case |
Time Complexity |
|
Best Case |
O(1) |
|
Average Case |
O(n) |
|
Worst case |
O(n) |
- Best Case Complexity in Linear Search: In Linear Search, best case occurs when the element we're looking for is at the top of the array. The time complexity of Linear Search in the best-case scenario is O (1).
- Average Case Complexity: In Linear Search, the average case time complexity is O(n).
- Worst Case Complexity: The worst case in Linear Search occurs when the element we're seeking for is at the end of the array. When the target element is not present in the specified array, the worst-case scenario is that we must traverse the entire array. The time complexity of Linear Search in the worst-case scenario is O(n).
Because each member in the array is only compared once, Linear Search has an O(n) time complexity.
Space Complexity of Linear Search in C Program
According to their input size, space complexity is essentially a measurement of the total amount of memory that algorithms or operations require. It is the amount of memory space required by the algorithm to solve a specific instance of the computational problem as a function of the input characteristics.
As we know that the amount of extra data in the Linear Search is fixed, the space complexity is always O(1).
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Conclusion
In C, Linear Search involves traversing a list or array sequentially to see if an entry is there. The goal is to begin traversing the array and compare items of the array one by one, starting with the first element, until a match is discovered or the array's end is reached.
We hope this article helped you gain knowledge of the C program for Linear Search. In this article, we discussed the uses of a Linear Search, time and space complexity, and approach to implement Linear Search in a code. We also learned how we can use it in our software development projects.
To know more about the Linear Search in C Program, you can enroll in the Post-Graduate Program in Full-Stack Web Development offered by Simplilearn in collaboration with Caltech CTME. This Web Development course is a descriptive online bootcamp that includes 25 projects, a capstone project, and interactive online classes. In addition to Linear Search in C Program and other related concepts, the course also details everything you need to become a full-stack technologist and accelerate your career as a software developer.
Simplilearn also offers free online skill-up courses in several domains, from data science and business analytics to software development, AI, and machine learning. You can take up any of these free courses to upgrade your skills and advance your career.