Linear Search in C

There are different types of searching in C, including linear search, a basic method that sequentially checks each element of a list until it finds the key element or the entire list has been traversed, hence known as sequential search. What is linear search in C? It checks each element of a list one by one until it finds the key element or the entire list has been traversed. The time complexity of the linear search algorithm in C is O(n) and space complexity is O(1). Other simple searching algorithms in C include Binary Search, Interpolation Search, and Hashing, which are also worth exploring.

Approach to Implement Linear Search Algorithm in C

• Take input of the element that is going to be searched. It can be referred to as a key element.
• Compare every element of the list with the key element starting from the leftmost end of the list.
• If any element of the list matches with the key, return the index of that element.
• If the entire list has been traversed and none of the elements matched with the key, then return -1 which specify the key element is not present in the list.

Flow Chart of the Linear Search Algorithm

Implementation of Linear Search Program in C

Below code will search the key element in the input array using linear search program in C using array.

Output:

Explanation:

• Declaration of an array and other variables.
• Take the input of the size of the array.
• Take the input of the array with help of a loop.
• Take the input of the element to search for ie. key element.
• The array will be traversed with the help of a loop from 0 to size-1.
  • Inside the loop, Apply a condition that whether the current element is equal to the key element or not
  • If the current element matches with the key element then get out of the loop using a break statement and if is not matched, the condition keeps checking the elements until the end of the array.
• After the cursor gets out of the loop, check whether the previous loop traversed the array partially or not with the help of a condition that the index of the previous loop is less than the size of the array or not.
• If the condition returns true then print the index of the key element.
• If the condition returns false then print the key element not found.

Time Complexity:

The time required to search an element using a linear search algorithm depends on the size of the array as the whole array is being traversed. In the best-case scenario, the key element is caught at the beginning of the array, and in the worst case, each element is being compared and the last one is the key element. Therefore, The time complexity of a linear search algorithm in C is O(n).

Space Complexity:

Space Complexity is O(1) as no extra space is being taken.

Linear Search in C for Multiple Occurrences

The previous code was designed because the key element occurs only once in the array. Here, the linear search algorithm in C is going to be modified for the multiple occurrences of the key element. The code is designed to find the number of occurrences of the key element in the array along with their positions.

Output:

Explanation:

• Declaration of an array and other variables.
• Initializing a variable ‘county’ to 0 which track the occurrences of the key element.
• Take the input of the size of the array.
• Take the input of the array with help of a loop.
• Take the input of the element to search for ie. key element.
• The array will be traversed with the help of a loop from 0 to size-1.
  • Inside the loop, Apply a condition that whether the current element is equal to the key element or not
  • If the current element matches with the key element then print the index of the key element and increment the variable ‘county’.
• After the cursor gets out of the loop, check whether the key element is found or not with the help of a condition that the variable cocountys equal to 0 or not
• If the condition returns true then the key element is not found.
• If the condition returns false then print the number of times the key element occurred while traversing the array.

Time Complexity: The time complexity of a linear search algorithm in C is O(n).

Space Complexity: Space Complexity is O(1) as no extra space is being taken.

Program for Linear Search in C Using a Function

Here, the main function calls another function for searching the key element in the array, forming a linear search program in C using function. The function takes an array, its size, and the key element as arguments and returns an index or -1 to the main function.

Output:

Explanation:

• Declaration of an array and other variables.
• Take the input of the size of the array.
• Take the input of the array with help of a loop.
• Take the input of the element to search for ie. key element.
• A variable ‘index’ calls a function ‘linear search()’ with the arguments as the array, its size and the key element.
• The function ‘linearSearch()’ contains the procedure of searching the key element in the array. The function will return the index of the key element is found or else -1 and store the value in the variable ‘index’ of the main function.
• In the function linear Search():
  • The array will be traversed with the help of a loop from 0 to size-1.
    • Inside the loop, Apply a condition that whether the current element is equal to the key element or not
    • If the current element matches with the key element then return the index of the key element.
  • After the cursor gets out of the loop, return -1 indicating that the key element is not found.
• The value returned from the function gets stored in the variable ‘index’.
• Now, check whether the variable index contains -1 or not. This is done to check whether the key value is found or not.
• If the condition returns true then print the key element not found.
• If the condition returns false then print the index of the key element.
• Time Complexity: O(n)
• Space Complexity: O(1)

Linear Search Function Using Pointers

Here, the linear search function is going to use the array through pointers. The function takes the pointer of the array as one of the arguments instead of the whole array. The traversal of the array is also performed using pointers.

Explanation:

• In the above code, a pointer of an array, its size and the key elements are taken as the arguments of the linear search function.
• In the function linearSearch():
  • The array will be traversed with the help of a pointer using a loop from 0 to size-1.
    • Inside the loop, Apply a condition that whether the current element is equal to the key element or not
    • The current element is represented through the pointer as (arr+index).
    • If the current element matches with the key element then return the key element.
  • After the cursor gets out of the loop, return -1 indicating that the key element is not found.