Count Comparisons in a Linear Search
Solve this ProblemEasy10 min
Topics
BasicsComplexityArraysSearching
Companies
TCSInfosysWipro
A linear search checks the elements of
nums from left to right and stops at the first one equal to target. Return how many comparisons it makes — the position of the first match plus one, or the full length if the target is absent.
Time complexityTime ComplexityHow the number of steps an algorithm takes grows as the input size n grows. describes how this count grows with the input size. For the same n, different inputs need different work: one comparison in the best caseBest CaseThe input that makes an algorithm do the least work., n in the worst caseWorst CaseThe input that makes an algorithm do the most work. Big-O usually describes this case.. We usually quote the worst case, so linear search is O(n).
Test Case 1:
Input:nums = [8, 3, 5, 3], target = 5
Output:3
Explanation:The search compares with 8, then 3, then 5 — found on the third comparison.
Test Case 2:
Input:nums = [8, 3, 5], target = 9
Output:3
Explanation:Not present: every element is compared once before the search gives up.
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
-1000000 ≤ nums[i], target ≤ 1000000
Try the Dry Run
Approach & Solutions
Scan Everything, Remember the First MatchGood
A linear search compares the target with each element from the left and stops at the first match. So it makes (position of the first match + 1) comparisons, or nums.length if the target is missing. This version finds that first position by scanning the whole array.
Time
O(n)Space
O(1)Java
class Solution {
public int comparisonsToFind(int[] nums, int target) {
int firstMatch = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target && firstMatch == -1) {
firstMatch = i;
}
}
return firstMatch == -1 ? nums.length : firstMatch + 1;
}
}Stop at the First MatchOptimal
Run the linear search itself and count as it goes: compare with each element and return i + 1 the moment one matches. If the loop ends without a match, every element was compared, so return the length. On lucky inputs it finishes almost immediately.
Time
O(n) worst, O(1) bestSpace
O(1)Java
class Solution {
public int comparisonsToFind(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i + 1;
}
}
return nums.length;
}
}