Linear Search for a Value
Solve this ProblemEasy5 min
Topics
BasicsArraysSearching
Companies
TCSInfosysWipro
Given an array
nums of distinct values and a target, return the index where the target appears, or -1 if it is not in the array.
Linear searchLinear SearchChecking elements one by one from the start until the target is found or the array ends. Works on any array, sorted or not. is the most basic search there is: walk through the array in order and compare. It needs no preparation and works on unsorted data, at the price of up to n comparisons. Returning a sentinel valueSentinel ValueA special return value, like −1, that cannot be a real answer and therefore signals "no result". like −1 is the standard way to report "not found".
Test Case 1:
Input:nums = [14, 3, 27, 8], target = 27
Output:2
Explanation:27 sits at index 2.
Test Case 2:
Input:nums = [14, 3, 27, 8], target = 5
Output:-1
Explanation:−1 is the usual signal for "not found".
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
all values in nums are distinct - ◆
-1000000 ≤ nums[i], target ≤ 1000000
Try the Dry Run
Approach & Solutions
Check Each IndexOptimal
Visit the indexes 0, 1, 2, … in order and compare each element with the target. Return the index as soon as they match. If the loop ends without a match, return −1, a value that can never be a real index.
Time
O(n)Space
O(1)Java
class Solution {
public int linearSearch(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
}Built-in Index LookupGood
Use the library's search: indexOf on a List in Java, index() in Python (guarded by an in-check, since index raises an error when the value is missing), std::find in C++ and indexOf in JavaScript. All of them scan from the left, just like the loop. C keeps the loop.
Time
O(n)Space
O(1)Java
class Solution {
public int linearSearch(int[] nums, int target) {
List<Integer> list = new ArrayList<>();
for (int v : nums) {
list.add(v);
}
return list.indexOf(target);
}
}