Given an integer array nums and an integer target, return the first index at which target occurs.
Return -1 when target is not present in the array.
Example 1
Input: nums = [10, 20, 30, 40, 50], target = 30
Output: 2
Explanation: The target element 30 is present at index 2, so the answer is 2.
Example 2
Input: nums = [5, 8, 12, 16], target = 10
Output: -1
Explanation: The target element 10 is not present in the array, so the answer is -1.
Approach
Traverse the array from left to right and compare each element with target.
Return the current index as soon as a match is found. If the traversal ends without finding target, return -1.
Algorithm
Traverse
numsfrom left to right so that the earliest occurrence oftargetis checked first.Compare the current element
nums[index]withtargetto see whether the required value has been found.If both values are equal, return
indeximmediately. Since the traversal starts from index0, this is guaranteed to be the first occurrence.If the current element does not match, continue with the next index and repeat the same check.
Return
-1after the traversal finishes, as reaching the end meanstargetdoes not exist in the array.
Dry Run
Linear Search Dry Run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int linearSearch(const vector<int>& nums, int target) { // Check elements from left to right to find the first match. for (int index = 0; index < nums.size(); index++) { // Return as soon as the target is found. if (nums[index] == target) { return index; } } // Reaching here means the target is not present. return -1; }};int main() { vector<int> nums = {4, 2, 7, 2}; int target = 2; Solution solution; int answer = solution.linearSearch(nums, target); cout << "Index: " << answer << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the number of elements in the array. In the worst case, the target is absent or appears at the final index.
Space Complexity: O(1), because no additional data structure is required.
FAQs
Q1. Why is the index returned immediately after finding a match?
The array is checked from left to right, so the first match has the smallest index.
Q2. Does linear search require the array to be sorted?
No. Each element is checked individually, so the approach works for both sorted and unsorted arrays.
Q3. What is returned when the target appears multiple times?
The index of its first occurrence is returned.
Q4. What is returned for an empty array?
The result is -1 because the array contains no matching element.
Q5. When can binary search be used instead?
Binary search can be used when the array is sorted. It reduces the search time to O(log N).
Be the first to add a comment.