Linear Search Examples in C++

📚 Quick Study Guide

• 🔍 Linear Search Definition: Also known as sequential search, it's a simple search algorithm that checks each element in a list until the desired element is found or the end of the list is reached.
• ⏱️ Time Complexity: The worst-case and average-case time complexity is $O(n)$, where $n$ is the number of elements in the list. The best-case time complexity is $O(1)$ when the target element is the first element in the list.
• 🧠 How it works:
  1. Start from the first element of the array.
  2. Compare each element with the target value.
  3. If a match is found, return the index of the element.
  4. If the end of the array is reached without finding a match, return -1 (or another indicator of 'not found').
• 💻 C++ Implementation Snippet: cpp int linearSearch(int arr[], int n, int target) { for (int i = 0; i < n; i++) { if (arr[i] == target) { return i; // Element found at index i } } return -1; // Element not found }
• 📈 Use Cases: Useful for unsorted lists or when the list is small, as it doesn't require pre-sorting.

Practice Quiz

1. What is the worst-case time complexity of linear search?
   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n^2)
2. In linear search, when is the best-case time complexity achieved?
   1. When the target element is the last element.
   2. When the target element is not in the list.
   3. When the target element is the middle element.
   4. When the target element is the first element.
3. What does linear search return if the target element is not found in the array?
   1. 0
   2. The last index of the array.
   3. -1
   4. The array size.
4. Which of the following scenarios is linear search most suitable for?
   1. Searching a large sorted array.
   2. Searching a small unsorted array.
   3. Searching a binary search tree.
   4. Searching a hash table.
5. Consider an array `arr = {5, 10, 15, 20, 25}`. What index will linear search return if `target = 15`?
   1. 0
   2. 1
   3. 2
   4. 3
6. Which of the following is a drawback of linear search?
   1. Requires the array to be sorted.
   2. Inefficient for large datasets.
   3. Complex to implement.
   4. Only works with integer arrays.
7. What is another name for linear search?
   1. Binary Search
   2. Sequential Search
   3. Jump Search
   4. Interpolation Search