linear search in c

Linear Search in C/C++

Linear Search

Linear Search in C/C++ means to sequentially traverse a given list or array and check if an element is present in the respective array or list. The idea is to start traversing the array and compare elements of the array one by one starting from the first element with the given element until a match is found or the end of the array is reached.

Examples :

Input : arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
          key = 110;
Output : 6
Element 110 is present at index 6

Input : arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
           key = 175;
Output : -1
Element 175 is not present in arr[].

Problem in Linear Search

Given an array arr[] of N elements, write a function for Linear Search in C to search a given element X in arr[].

Algorithm:

  • Start from the leftmost element of arr[] and one by one compare X with each element of arr[].
  • If X matches with an element, return the index.

If X doesn’t match with any of elements and end of the array is reached, return -1

// Function to linearly search the element X in the 
// array arr[] of N elements
int search(int arr[], int N, int X) 
{    
    // Pointer to traverse the array
    int i; 

    // Start traversing the array
    for (i = 0; i < N; i++) 
    {   
        // If a successful match is found,
        // return the index
        if (arr[i] == X) 
            return i; 
    }

    // If the element is not found,
    // and end of array is reached
    return -1; 
}

Time Complexity

O(N). Since we are traversing the complete array, so in worst case when the element X does not exists in the array, number of comparisons will be N. Therefore, worst case time complexity of the linear search algorithm is O(N).

Improving the Time Complexity

We can improve the worse case time complexity to a average level.

  1. if element Found at last  O(n) to O(1)
  2. if element Not found O(n) to O(n/2)

Implementation idea

The worst case scenario occurs only when the element happens to be present in the last index. To solve this problem, we follow the below steps to average the time complexity.

  1. Assign the first most value to a variable called “left”.
  2. Likewise assign the last indexed value to a variable called “right”.
  3. Now as usual we run a for loop.
  4. Inside the for loop check for the two condition if the value-to-be-searched is either left or right most variable. If so, the task becomes simpler.
  5. By applying this condition, we can improve the time complexity.

Example

Let’s see the coding in C++. The same applies for C too.

using namespace std; 
  
void search(vector<int> arr, int search_Element) 
{ 
    int left = 0; 
    int length = arr.size(); 
    int position = -1; 
      int right = length - 1; 
        
    // Run loop from 0 to right 
    for(left = 0; left <= right;)  
    { 
          
        // If search_element is found with 
        // left varaible 
        if (arr[left] == search_Element)  
        { 
              
            position = left; 
            cout << "Element found in Array at "
                 << position + 1 << " Position with "
                 << left + 1 << " Attempt"; 
                 
            break; 
        } 
        
        // If search_element is found with 
        // right varaible 
        if (arr[right] == search_Element)  
        { 
            position = right; 
            cout << "Element found in Array at "
                 << position + 1 << " Position with "
                 << length - right << " Attempt"; 
                 
            break; 
        } 
        left++; 
        right--; 
    } 
  
    // If element not found 
    if (position == -1) 
        cout << "Not found in Array with "
             << left << " Attempt"; 
} 
  
// Driver code 
int main() 
{ 
    vector<int> arr{ 1, 2, 3, 4, 5 }; 
    int search_element = 5; 
      
    // Function call 
    search(arr, search_element); 
} 

Conclusion

Array concept can be a very easy and interesting one when you learn to code easily. For that, you need basic knowledge. Hope this article helped you to understand the basic concepts of linear search of array!

Sudhanshu is Technology geek and also a pro pubg player. I like to create content in my free time that helps others. Currently pursuing BCA from Noida and operating Geekstocode

Leave a Comment

Your email address will not be published. Required fields are marked *