Linear Search Algorithm in DSA Java

Mental Model

Look at each item one by one until you find the one you want or reach the end.

Analogy: Imagine looking for a book on a shelf by checking each book from left to right until you find the right one.

Array: [3] -> [7] -> [1] -> [9] -> [5] -> null
Search for: 9
Start at index 0 ↑

Dry Run Walkthrough

Input: array: [3, 7, 1, 9, 5], search value: 9

Goal: Find the index of value 9 in the array or return -1 if not found

Step 1: Check element at index 0

[3] ↑ -> [7] -> [1] -> [9] -> [5] -> null

Why: Start from the first element to see if it matches the search value

Step 2: Check element at index 1

[3] -> [7] ↑ -> [1] -> [9] -> [5] -> null

Why: First element was not 9, move to next element

Step 3: Check element at index 2

[3] -> [7] -> [1] ↑ -> [9] -> [5] -> null

Why: Keep checking next element until match or end

Step 4: Check element at index 3

[3] -> [7] -> [1] -> [9] ↑ -> [5] -> null

Why: Found the element 9, stop searching

Result:

[3] -> [7] -> [1] -> [9] ↑ -> [5] -> null
Found at index 3

Annotated Code

DSA Java

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

    public static void main(String[] args) {
        int[] array = {3, 7, 1, 9, 5};
        int target = 9;
        int result = linearSearch(array, target);
        if (result == -1) {
            System.out.println("Value not found");
        } else {
            System.out.println("Found at index " + result);
        }
    }
}

for (int i = 0; i < arr.length; i++) {

iterate over each element in the array

if (arr[i] == target) {

check if current element matches the target

return i; // found target at index i

stop and return index when target is found

return -1; // target not found

return -1 if target is not in the array

Output

Found at index 3

Complexity Analysis

Time: O(n) because in the worst case we check each element once

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to binary search which is O(log n), linear search is slower but works on unsorted arrays

Edge Cases

empty array

returns -1 immediately since there are no elements

DSA Java

for (int i = 0; i < arr.length; i++) {

target not in array

returns -1 after checking all elements

DSA Java

return -1; // target not found

target is first element

returns index 0 immediately

DSA Java

if (arr[i] == target) {

When to Use This Pattern

When you need to find an item in a list without any order, use linear search because it checks each item one by one.

Common Mistakes

Mistake: Stopping the search too early without checking all elements
Fix: Only stop when you find the target or finish checking all elements

Mistake: Returning index before confirming the element matches the target
Fix: Always check if arr[i] == target before returning index

Summary

It looks through each element in order to find a target value.

Use it when the list is unsorted or small.

The key is to check every element one by one until you find the target.

Practice

1. What is the main idea behind the Linear Search Algorithm?

easy

A. Sort the list first then search using binary method

B. Divide the list into halves repeatedly to find the target

C. Use a hash table to find the target instantly

D. Check each element one by one until the target is found or list ends

Solution

1. Step 1: Understand linear search process

   Linear search checks each element in order from start to end.

2. Step 2: Compare with other search methods

   Binary search divides list, hash uses extra memory, linear is simple sequential check.

3. Final Answer:

   Check each element one by one until the target is found or list ends -> Option D

4. Quick Check:

   Linear search = sequential check [OK]

Hint: Linear search checks elements one by one [OK]

Common Mistakes:

• Confusing linear search with binary search
• Thinking linear search requires sorted list
• Assuming linear search uses extra memory

2. Which of the following is the correct syntax to start a linear search loop in Java for an array arr of length n?

easy

A. for (int i = 0; i < n; i++)

B. for (int i = 0; i <= n; i++)

C. for (int i = 1; i < n; i++)

D. for (int i = 1; i <= n; i++)

Solution

1. Step 1: Understand array indexing in Java

   Java arrays start at index 0 and go up to n-1, so loop must run from 0 to less than n.

2. Step 2: Check loop conditions

   for (int i = 0; i < n; i++) uses i = 0 to i < n, which covers all valid indices correctly.

3. Final Answer:

   for (int i = 0; i < n; i++) -> Option A

4. Quick Check:

   Array index 0 to n-1 = for loop i=0 to i<n [OK]

Hint: Array indices start at 0, loop till less than length [OK]

Common Mistakes:

• Using <= n causes index out of bounds error
• Starting loop at 1 misses first element
• Confusing array length with last index

3. What will be the output of the following Java code?

int[] arr = {4, 8, 15, 16, 23, 42};
int target = 15;
int index = -1;
for (int i = 0; i < arr.length; i++) {
  if (arr[i] == target) {
    index = i;
    break;
  }
}
System.out.println(index);

medium

A. 0

B. -1

C. 2

D. 3

Solution

1. Step 1: Loop through array to find target 15

   Indices: 0=4, 1=8, 2=15. At i=2, arr[i] == 15 matches target.

2. Step 2: Assign index and break loop

   index is set to 2 and loop stops immediately.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Target 15 found at index 2 [OK]

Hint: Stop loop when target found, print index [OK]

Common Mistakes:

• Not breaking loop causes last index output
• Printing target value instead of index
• Confusing index with array value

4. Identify the error in the following linear search code snippet and choose the correct fix:

int[] arr = {1, 3, 5, 7};
int target = 5;
int index = -1;
for (int i = 1; i <= arr.length; i++) {
  if (arr[i] == target) {
    index = i;
    break;
  }
}
System.out.println(index);

medium

A. Change loop to: for (int i = 0; i <= arr.length; i++)

B. Change loop to: for (int i = 0; i < arr.length; i++)

C. Change loop to: for (int i = 1; i < arr.length; i++)

D. No change needed, code is correct

Solution

1. Step 1: Identify loop index error

   Loop starts at 1 and goes to i <= arr.length, which causes index out of bounds at i = arr.length.

2. Step 2: Correct loop to valid indices

   Loop should start at 0 and run while i < arr.length to cover all valid indices safely.

3. Final Answer:

   Change loop to: for (int i = 0; i < arr.length; i++) -> Option B

4. Quick Check:

   Loop indices 0 to length-1 avoid errors [OK]

Hint: Loop from 0 to less than length to avoid errors [OK]

Common Mistakes:

• Using <= arr.length causes runtime error
• Starting loop at 1 misses first element
• Ignoring array index bounds

5. You have an array arr = {2, 4, 7, 6, 8, 10}. You want to find the index of the first even number greater than 5 using linear search. Which code snippet correctly implements this?

hard

A. for (int i = 0; i < arr.length; i++) { if (arr[i] > 5 && arr[i] % 2 == 0) { System.out.println(i); break; } }

B. for (int i = 0; i < arr.length; i++) { if (arr[i] % 2 == 0) { System.out.println(i); break; } }

C. for (int i = 0; i < arr.length; i++) { if (arr[i] > 5) { System.out.println(i); break; } }

D. for (int i = 0; i < arr.length; i++) { if (arr[i] < 5 && arr[i] % 2 == 0) { System.out.println(i); break; } }

Solution

1. Step 1: Understand the condition to find

   We want the first element that is even and greater than 5.

2. Step 2: Check each option's condition

   for (int i = 0; i < arr.length; i++) { if (arr[i] > 5 && arr[i] % 2 == 0) { System.out.println(i); break; } } checks both conditions correctly; others miss one or use wrong condition.

3. Final Answer:

   for (int i = 0; i < arr.length; i++) { if (arr[i] > 5 && arr[i] % 2 == 0) { System.out.println(i); break; } } -> Option A

4. Quick Check:

   Check both conditions with && for correct index [OK]

Hint: Use && to combine conditions in linear search [OK]

Common Mistakes:

• Checking only one condition instead of both
• Using || instead of && causing wrong matches
• Not breaking loop after first match