Problem Statement

Given an array of integers nums and an integer target, find the smallest index (0 based indexing) where the target appears in the array. If the target is not found in the array, return -1.

Examples

Example 1:

Input: nums = [2, 3, 4, 5 , 7], target = 4
Output: 2

Explanation: The first occurrence of the 4 is at index 2.

Example 2:

Input: nums = [-2, -3, 4, 5, 7], target = 6
Output: -1

Exaplanation: The value 6 does not exist in the nums array.

Approaches

1️⃣ Traverse Linearly

Intuition:

Lets 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:

1. Traverse through the array, similar to the idea of scanning each book serially.
2. Check if the current element of array is equal to the target element. If so, return the index and stop scanning further.
3. In case target value is not found, return -1 marking that the target element missing.

Dry Run:

Initialization:

Target = 3

      -------------------------------
nums  |  7  |  6  |  3  |  2  |  1  |
      -------------------------------
         0     1     2     3     4

First Iteration:

      -------------------------------
nums  |  7  |  6  |  3  |  2  |  1  |
      -------------------------------
         0     1     2     3     4
         i

nums[i] == Target
nums[0] == 3
7 == 3
false

To the next iteration, i++

Second Iteration:

      -------------------------------
nums  |  7  |  6  |  3  |  2  |  1  |
      -------------------------------
         0     1     2     3     4
               i

nums[i] == Target
nums[1] == 3
6 == 3
false

To the next iteration, i++

Third Iteration:

      -------------------------------
nums  |  7  |  6  |  3  |  2  |  1  |
      -------------------------------
         0     1     2     3     4
                     i

nums[i] == Target
nums[2] == 3
3 == 3
true

break the loop and return i, which is 2.

Code:

#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;
}

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.