C Linear Search Program
Linear search is a straightforward searching algorithm used to find a specific element in a list or array. The algorithm sequentially checks each element of the list until it finds the target value or reaches the end of the list. This method is simple to implement and works well for small datasets or unsorted arrays.
Key Characteristics of Linear Search
Time Complexity:
- The worst-case and average-case time complexity of linear search is , where is the number of elements in the array. In the best case, the element is found on the first attempt, leading to a time complexity of .
Space Complexity:
- The space complexity of linear search is since it uses a constant amount of additional space regardless of the input size.
Use Cases:
- Linear search is suitable for small or unsorted datasets. It is not efficient for large datasets compared to more advanced algorithms like binary search.
Implementation of Linear Search in C
Below is a simple implementation of the linear search algorithm in C.
Explanation of the Code
Header Files:
#include <stdio.h>
: Includes the standard input-output library for functions likeprintf
andscanf
.
Linear Search Function:
- The function
linearSearch
takes three parameters:- An integer array
arr[]
, - An integer
size
representing the number of elements in the array, - An integer
target
which is the value to search for.
- An integer array
- The function iterates over each element of the array:
- If the current element matches the target, it returns the index of that element.
- If the loop completes without finding the target, it returns
-1
indicating that the element is not present in the array.
- The function
Main Function:
- Initializes an example array
arr
with some integers. - Calculates the size of the array using
sizeof(arr) / sizeof(arr[0])
. - Prompts the user to enter a number to search for.
- Calls the
linearSearch
function and stores the result. - Displays the index of the found element or a message indicating that the element is not found.
- Initializes an example array
How to Run the Program
Compile the Code: Use a C compiler like
gcc
to compile the code.Execute the Program:
Input Data: Enter a number when prompted to see if it exists in the array.
Example Input/Output
Input:
Output:
Input:
Output:
Conclusion
Linear search is a fundamental algorithm that is easy to understand and implement. It is best used for small or unsorted datasets due to its linear time complexity. While it is not the most efficient searching method for large datasets, it serves as an excellent introduction to search algorithms in programming.