Intuition:

Let's break the problem statement into an example to understand it better. Imagine having a long shelf filled with books, and each book has a unique number written on its spine. The ask is to look for the first book with a specific number, let's say 2.

To achieve this we will simply start scanning each book and once a book with number 2 is got, stop the scan procedure.

Approach

Traverse through the array, similar to the idea of scanning each book serially.

Check if the current element of array is equal to the target element. If so, return the index and stop scanning further.

In case target value is not found, return -1 marking that the target element missing.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
// Linear Search Function
    int linearSearch(vector<int>& nums, int target) {
        // Traverse the entire vector
        for (int i = 0; i < nums.size(); i++) {
            // Check if current element is target
            if (nums[i] == target) {
                // Return index
                return i;
            }
        }
        // If target not found
        return -1;
    }
};

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int target = 4;

    // Create an instance of the Solution class
    Solution sol;

    // Call the linearSearch method
    int result = sol.linearSearch(nums, target);

    // Print the result
    cout << result << endl;

    return 0;
}

import java.util.*;
class Solution {
// Linear Search Function
    public int linearSearch(int[] nums, int target) {
        // Traverse the entire array
        for (int i = 0; i < nums.length; i++) {

            // Check if current element is target
            if (nums[i] == target) {

                // Return if target found
                return i;

            }
        }
        // If target not found
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int target = 4;

        // Create an instance of the Solution class
        Solution sol = new Solution();

         // Call the linearSearch method
        int result = sol.linearSearch(nums, target);
        
        System.out.println(result);
    }
}

from typing import List

class Solution:
    # Linear Search Function
    def linearSearch(self, nums: List[int], target: int) -> int:
        # Traverse the entire array
        for i in range(len(nums)):

            # Check if current element is target
            if nums[i] == target:

                # Return index if target found
                return i

        # If target not found
        return -1

# Main function
if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    target = 4

    # Create an instance of the Solution class
    sol = Solution()

    # Call the linearSearch method and store the result
    result = sol.linearSearch(nums, target)
   
    print(result)
class Solution {
    linearSearch(nums, target) {
        // Traverse the entire array
        for (let i = 0; i < nums.length; i++) {

            // Check if current element is target
            if (nums[i] === target) {

                // Return if found
                return i;

            }
        }
        // If the target is not found
        return -1;
    }
}

const nums = [1, 2, 3, 4, 5];
const target = 4;

// Create an instance of the Solution class
const sol = new Solution();

// Call the linearSearch method and store the result
const result  =  sol.linearSearch(nums, target);

console.log(result);

Complexity Analysis

Time Complexity: O(N), in worst case entire array will be traversed, taking a time of N where N is size of the array. Space Complexity: O(1), as no additional space is used apart from the input array, the space complexity stays constant.

Problem List

Linear Search

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code