Linear Search Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Linear Search Algorithm?

Linear Search checks each item in a list one by one until it finds the target or reaches the end.

beginner

What is the time complexity of Linear Search in the worst case?

The worst-case time complexity is O(n), where n is the number of items in the list.

beginner

Show the basic steps of Linear Search in simple terms.

1. Start at the first item.<br>2. Compare it with the target.<br>3. If it matches, stop and return the position.<br>4. If not, move to the next item.<br>5. Repeat until found or list ends.

beginner

Why is Linear Search not efficient for large lists?

Because it checks every item one by one, it can take a long time if the list is big.

beginner

In which cases is Linear Search useful?

When the list is small or unsorted, or when simplicity is more important than speed.

What does Linear Search do first?

A Checks the first item in the list

B Sorts the list

C Divides the list in half

D Skips to the middle item

Linear Search starts by checking the first item in the list.

What is the worst-case time complexity of Linear Search?

A O(1)

B O(log n)

C O(n log n)

D O(n)

In the worst case, Linear Search checks all n items, so time complexity is O(n).

When does Linear Search stop?

A After checking half the list

B When the target is found or list ends

C After sorting the list

D After checking the middle item

Linear Search stops when it finds the target or reaches the end of the list.

Which list type is Linear Search best suited for?

A Unsorted or small lists

B Sorted lists

C Very large lists

D Lists with duplicates only

Linear Search works well for small or unsorted lists where simplicity matters.

What happens if the target is not in the list?

A Linear Search crashes

B Linear Search returns the last item

C Linear Search returns -1 or not found

D Linear Search sorts the list

If the target is not found, Linear Search returns a special value like -1 to show it is missing.

Explain how Linear Search works step-by-step.

Think about checking items one by one.

Describe when and why you would use Linear Search instead of other search methods.

Consider list size and order.