Linear Search Algorithm in DSA Java - Execution Trace

Concept Flow - Linear Search Algorithm

Start at index 0

↓

Check if element at index == target?

No→Move to next index

↓

Index < array length?

No→Not found

↓

Return index

Start from the first element, check each one until you find the target or reach the end.

Execution Sample

DSA Java

int linearSearch(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;
  }
  return -1;
}

Searches each element in the array one by one to find the target value.

Execution Table

Step	Operation	Index Checked	Element at Index	Target	Match?	Action	Result/Return
1	Check element	0	4	3	No	Move to next index
2	Check element	1	2	3	No	Move to next index
3	Check element	2	3	3	Yes	Return index	2

💡 Target found at index 2, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
i	0	1	2	2	2
arr[i]	4	2	3	3	3
target	3	3	3	3	3
result	undefined	undefined	undefined	2	2

Key Moments - 3 Insights

Why does the search stop immediately when a match is found?

Because the algorithm returns the index as soon as arr[i] == target is true, as shown in step 3 of the execution_table.

What happens if the target is not in the array?

The loop completes without finding a match, then returns -1 after checking all elements, which is not shown here but would be after the last index check.

Why do we check each element one by one instead of jumping to a random index?

Linear search checks every element sequentially because the array is unsorted, so we cannot skip any elements safely, as shown by the stepwise index checks in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' when the target is found?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'Index Checked' column in the row where 'Match?' is 'Yes'.

At which step does the algorithm return the index?

A Step 1

B Step 2

C Step 3

D After all steps

💡 Hint

Look at the 'Action' and 'Result/Return' columns in the execution_table.

If the target was 5 instead of 3, what would happen in the execution_table?

A The search would return index 2

B The search would return -1 after checking all elements

C The search would stop at index 0

D The search would return index 1

💡 Hint

Think about what happens when no element matches the target in the loop.

Concept Snapshot

Linear Search Algorithm:
- Start at first element (index 0)
- Check each element one by one
- If element == target, return index immediately
- If end reached without match, return -1
- Works on unsorted arrays, simple but slow for large data

Full Transcript

Linear search starts at the first element of the array and checks each element in order. If the current element matches the target, it returns the index immediately. If it reaches the end without finding the target, it returns -1. This method is simple and works on any array but can be slow if the array is large because it checks every element one by one.

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