Linear Search

Linear search is the simplest searching algorithm in which we search the element one by one from starting to end and exit when the element is found or return not_found if the element was not found.

Since we are iteratively moving through the whole input one by one, the time complexity for this algorithm would be O(n).

Since we are not using any extra memory than the given array and the element we have to search from, the space complexity is O(1).

Code

bool linear_search(vector<int> &vec, int target) {
  for(int i = 0; i < vec.size(); i++) {
    if(arr[i] == target) {
      return true
    }
  }
  return false;
}