Linear Search

Lesson 9 of 26 in Coddy's Arrays in C++ course.

To search for a required element in an array, we use a simple method called linear search.

As the name suggests it takes linear time means O(n) time to search an element as we have to iterate through the whole array in order to get the required number.

Suppose k is the element that we have to find and an array is given. we have to iterate through the whole array and if we found the element we have to print YES, or else we print NO.

for(int i=0;i<n;i++){
   if(arr[i]==k){
     cout<<"YES"<<endl;
   }else{
     cout<<"NO"<<endl;
   }
}

Analyzing time complexity

The best case that can happen is the element that we are finding can be on the first index, in that case, it will take constant time. But the worst can happen is if the element is on the last index then time complexity becomes in order on n. Therefore the time complexity of the linear search is O(n) where n is the number of elements in an array.

Challenge

Given an array find the sum of all elements in the array.

Try it yourself

#include<iostream>
using namespace std;

int main(){

 
  int n;
  cin>>n;

  int arr[n];
  
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  

 //Write your code here 





    return 0;
}