logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
Check if Array is SortedLargest Element in an ArrayArray Rotation (Left and Right)Left Rotate Array by OneLinear SearchMax Consecutive OnesSecond Largest Element in an ArraySingle Number
Code Scratch/take u forward/arrays/fundamentals

Linear Search

5 min read
On this pageQuestion
QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up

tags:

  • cc
  • array
  • linear-search

# Question

Given an array of integers numsnumsnums and an integer targettargettarget, find the smallest index (0-indexed) where the targettargettarget appears. If the targettargettarget is not present, return −1-1−1.

nums=[2,3,4,10,40]nums = [2, 3, 4, 10, 40]nums=[2,3,4,10,40], target=10→Output: 3target = 10 \rightarrow \text{Output: } 3target=10→Output: 3

# Solution

# Pattern

Linear Scan The algorithm checks each element of the sequence sequentially until a match is found or the end of the sequence is reached.

# How to Identify

  • When the data is unsorted.
  • When you need to find the first occurrence of an element.
  • When the input size is small enough that O(n)O(n)O(n) is acceptable.
  • When no additional data structures (like HashMaps) are allowed.

# Description

Step-by-step explanation:

  1. Boundary Check: First, ensure the input array is not null or empty.
  2. Traversal: Start from the first element (index 000).
  3. Comparison: Compare the current element nums[i]nums[i]nums[i] with the targettargettarget.
  4. Early Exit: If nums[i]==targetnums[i] == targetnums[i]==target, immediately return iii as the result. This ensures we find the smallest index.
  5. Exhaustion: If the loop completes and the end of the array is reached without a match, return −1-1−1.

# The Intuition

Think of Linear Search as looking for a specific book on a messy shelf. You don't know the order, so you must look at every spine one by one, starting from the left. You stop as soon as you find it. If you reach the right end of the shelf without seeing it, you conclude the book isn't there.

# Complexity

LabelWorstAverage
Time ComplexityO(n)O(n)O(n)O(n/2)O(n/2)O(n/2)
Space ComplexityO(1)O(1)O(1)O(1)O(1)O(1)

# Time Complexity

In the worst case, the target is the last element or not present, requiring nnn comparisons. Average case finds it in n/2n/2n/2 steps.

# Space Complexity

The algorithm is performed in-place with a constant amount of auxiliary memory (O(1)O(1)O(1)).

# Code

class Solution {
    /**
     * Finds the first occurrence of target in nums.
     * Uses a standard for-loop for maximum readability and thread safety.
     */
    public int linearSearch(int[] nums, int target) {
        // Handle edge cases
        if (nums == null || nums.length == 0) {
            return -1;
        }
 
        // Standard linear scan
        for (int i = 0; i < nums.length; i++) {
            // Return index as soon as target is matched
            if (nums[i] == target) {
                return i;
            }
        }
 
        // Target not found after full traversal
        return -1;
    }
}

# Caveats

  • Performance: For very large datasets requiring frequent searches, O(n)O(n)O(n) is inefficient. Use a HashSet or sort the data for O(1)O(1)O(1) or O(log⁡n)O(\log n)O(logn) search.
  • Data Types: For objects (e.g., String), use .equals() instead of ==.
  • Concurrency: Modifying the array during a search (Sentinel method) is dangerous in multi-threaded environments.

# Concepts to Think About

  • Cache Locality: Linear search is cache-friendly because it accesses elements contiguously in memory.

  • Search vs. Selection: Linear search is O(n)O(n)O(n), but finding the kkk-th smallest element (Selection) is a different problem usually solved by QuickSelect.

  • Early Exit Strategy: Always return immediately upon finding the result to optimize the average case.

  • Sorted Data: If the array were sorted, would you still use Linear Search? Think about why Binary Search (O(log⁡n)O(\log n)O(logn)) would be vastly superior for sorted datasets.

  • Search for All: How would the code change if the question asked for all indices where the target appears? (Hint: You would need a dynamic collection like a List to store results instead of returning immediately).

  • Sentinel Search: There is a variation called "Sentinel Linear Search" where you place the target at the very end of the array manually. Why would this reduce the number of comparisons made inside the loop?

    • Sentinel Linear Search is an optimized version of the basic search. By placing the target at the end of the array (the "sentinel"), we guarantee the loop will always find the target. This allows us to remove the boundary check (i < length) from the loop header, saving one comparison per iteration.
    • Imagine walking through a long hallway of doors looking for a specific person. Usually, you have to check two things at every door: "Is this the person?" AND "Have I reached the end of the hallway?" To save time, you put a clone of the person you're looking for at the very end of the hallway. Now, you only have to ask one question: "Is this the person?" When you find them, you just check if you're at the very last door to see if it was a real find or just your clone.
      class Solution {
          public int linearSearch(int[] nums, int target) {
              // Guardrail for empty arrays
              if (nums == null || nums.length == 0) return -1;
       
              int n = nums.length;
              int lastElement = nums[n - 1];
       
              // Place sentinel
              nums[n - 1] = target;
              int i = 0;
       
              // Optimized loop: No boundary check (i < n) required!
              while (nums[i] != target) {
                  i++;
              }
       
              // Restore the original last element
              nums[n - 1] = lastElement;
       
              // If we found the target before the last element, or if the 
              // original last element was actually the target, return the index.
              if (i < n - 1 || lastElement == target) {
                  return i;
              }
       
              return -1;
          }
      }
  • Order of Operations: If you are going to search the same unsorted array 1,000 times, is it better to do 1,000 Linear Searches, or sort the array once and do 1,000 Binary Searches? (Think about the O(n2)O(n^2)O(n2) total cost vs O(nlog⁡n+klog⁡n)O(n \log n + k \log n)O(nlogn+klogn)).

  • 2D Linear Search: If you were given a matrix instead of a flat array, what would the Time Complexity be? (O(rows×columns)O(rows \times columns)O(rows×columns)).

# Logical Follow-up

Question: If the array were sorted, how would you improve this? Solution: Use Binary Search. By repeatedly halving the search space, the complexity drops from O(n)O(n)O(n) to O(log⁡n)O(\log n)O(logn).

Question: How would you search for a target in a 2D Matrix? Solution: You can still use linear search (visiting every cell O(N×M)O(N \times M)O(N×M)), but if the matrix is sorted, you can optimize by starting from the top-right or bottom-left corner (O(N+M)O(N+M)O(N+M)).

←PreviousLeft Rotate Array by OneNext→Max Consecutive Ones

On this page

QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up