Linear Search

Linear search is the simplest searching algorithm. Imagine you're looking for your friend in a line of people - you start from the first person and check each one until you find your friend. That's exactly how linear search works!

It checks each element in a list one by one, from start to end, until it finds what you're looking for or reaches the end of the list.

How Does It Work?

Here's the simple process:

  1. Start at the first element
  2. Check if it matches what you're searching for
  3. If it matches, you're done! Return the position
  4. If it doesn't match, move to the next element
  5. Repeat until you find it or reach the end

Real-Life Example

Let's say you have a list of exam scores: [65, 80, 55, 90, 75]

You want to find if score 90 exists in the list.

Step by step:

  • Check position 0: Is 65 equal to 90? No, move forward
  • Check position 1: Is 80 equal to 90? No, move forward
  • Check position 2: Is 55 equal to 90? No, move forward
  • Check position 3: Is 90 equal to 90? Yes! Found it at index 3

Code Implementation

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        // Loop through each element
        for (int i = 0; i < arr.length; i++) {
            // If element matches target, return its index
            if (arr[i] == target) {
                return i;
            }
        }
        // If not found, return -1
        return -1;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 23, 45, 70, 11, 15};

        int result = linearSearch(numbers, 70);
        System.out.println(result); // Output: 3

        int notFound = linearSearch(numbers, 100);
        System.out.println(notFound); // Output: -1
    }
}

Time and Space Complexity

Time Complexity:

  • Best Case: O(1) - The element is at the first position
  • Average Case: O(n) - The element is somewhere in the middle
  • Worst Case: O(n) - The element is at the last position or not present

Space Complexity: O(1) - We only use a single variable for iteration

Use Linear Search when:

  • Your list is small (under 100 elements)
  • The list is unsorted
  • You only need to search once or rarely
  • Simplicity is more important than speed

Don't use Linear Search when:

  • Your list is very large (thousands of elements)
  • The list is sorted (use Binary Search instead)
  • You need to search many times (consider sorting first)

Advantages and Disadvantages

Advantages:

  • Very simple to understand and implement
  • Works on unsorted lists
  • Works on any type of data
  • No preprocessing needed

Disadvantages:

  • Slow for large datasets
  • Inefficient compared to other algorithms for sorted data
  • Every search takes potentially O(n) time

Must-Do LeetCode Questions

#ProblemDifficultyLink
1Check If N and Its Double ExistEasyLeetCode 1346
2Find Numbers with Even Number of DigitsEasyLeetCode 1295
3Valid Mountain ArrayEasyLeetCode 941
4Search in Rotated Sorted ArrayMediumLeetCode 33
5Find First and Last Position of Element in Sorted ArrayMediumLeetCode 34
6Search a 2D MatrixMediumLeetCode 74
7Search in Rotated Sorted Array IIMediumLeetCode 81
8Find Minimum in Rotated Sorted ArrayMediumLeetCode 153
9Peak Index in a Mountain ArrayMediumLeetCode 852
10Single Element in a Sorted ArrayMediumLeetCode 540

Summary

Linear search is your first step into the world of searching algorithms. While it's not the fastest, it's the most straightforward and works in all situations. Master it well, because understanding linear search will help you appreciate why other, more complex algorithms exist!

Key Takeaway: Linear search checks every element one by one until it finds what it's looking for. Simple, reliable, but can be slow for large datasets.