Linear Search Algorithm Lecture

Overview

• Linear search, also known as sequential search.
• Searches for an element by going through each item in a list until the desired element is found or the list ends.

Example and Explanation

• Data Array: [15, 5, 20, 35, 40, 42, 60, 70]
  • Number of elements (n) = 8
  • Indexes range from 0 to 7
• Search Element: Example of searching for 42
  • Possible Outcomes:
    • Element found: Print its index or position.
    • Element not found: Print an appropriate message.

Search Process

1. Start from index 0.
2. Compare each element with the search key.
3. If a match is found, print the index (or position) and stop the search.
4. If no match after reaching the end, print “element not found.”

Key Steps in Code

• Loop through array:
  • for (int i = 0; i < n; i++)
  • Compare array[i] with the search key.
  • If match found, print index and use break to exit early.
  • If loop completes without finding the element, print “element not found.”

Code Snippet

int linearSearch(int arr[], int n, int data) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == data) {
            printf("Element found at index %d\n", i);
            break;
        }
    }
    if (i == n) {
        printf("Element not found\n");
    }
}

Optimizations and Conditions

• Stopping Condition:
  • Found the element: break statement to exit the loop.
  • Reached end of array: Check if i == n.
• Example with Found variable:
  • Introduce a found flag to avoid another comparison outside the loop.
• Breakdown for 41 (not in array):
  • Loop completes without finding 41.
  • Use found flag to decide print statement.

Time Complexity

• Best Case: O(1) - Element at the first index.
• Worst Case: O(n) - Element at the last index or not present.
• Average Case:
  • Derived from sum of all comparisons divided by count of all cases, resulting in O(n).

Summary

• Linear search is simple but can be inefficient for large lists.
• Essential understanding for moving on to more advanced search methods like binary search.
• Next topic: Binary Search Algorithm.