Linear Search

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;  // Return index if found
        }
    }
    return -1;  // Return -1 if not found
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key;
    
    cout << "Array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    cout << "Enter element to search: ";
    cin >> key;
    
    int result = linearSearch(arr, n, key);
    
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found in array" << endl;
    }
    
    return 0;
}

Array: 64 34 25 12 22 11 90
Enter element to search: 25
Element found at index: 2

This program teaches you how to implement the Linear Search algorithm in C++. Linear Search is the simplest searching algorithm that sequentially checks each element of the array from the beginning until it finds the target element or reaches the end. It works on both sorted and unsorted arrays, making it versatile but inefficient for large datasets.

---

1. What This Program Does

The program searches for an element in an array using Linear Search. For example:

• Array: [64, 34, 25, 12, 22, 11, 90]
• Search for: 25
• Result: Element found at index 2

Linear Search checks each element one by one until it finds a match or exhausts all elements.

---

2. Header File Used

#include <iostream>

This header provides:

• cout for displaying output
• cin for taking input from the user

---

3. Understanding Linear Search

Algorithm Concept:

• Start from first element (index 0)
• Compare each element with target
• If match found, return index
• If end reached, return -1 (not found)

Visual Example:

Array: [64, 34, 25, 12, 22, 11, 90] Search for: 25

Step 1: Check arr[0] = 64 → not 25, continue Step 2: Check arr[1] = 34 → not 25, continue Step 3: Check arr[2] = 25 → match! Return index 2

---

4. Function: linearSearch()

int linearSearch(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return i; // Return index if found } } return -1; // Return -1 if not found }

How it works:

• Iterates through array from index 0 to n-1
• Compares each element with key
• Returns index if match found
• Returns -1 if key not found

---

5. Step-by-Step Algorithm

For each element in array:

Step 1: Check Current Element

• Compare arr[i] with key
• If equal: element found, return index i
• If not equal: continue to next element

Step 2: Move to Next Element

• Increment i
• Repeat comparison

Step 3: End of Array

• If i reaches n, all elements checked
• Key not found, return -1

Example (searching for 25):

• i=0: arr[0]=64 ≠ 25 → continue
• i=1: arr[1]=34 ≠ 25 → continue
• i=2: arr[2]=25 = 25 → found! Return 2

---

6. Time and Space Complexity

Time Complexity:

• Best case: O(1) - element at first position
• Worst case: O(n) - element at last position or not found
• Average case: O(n) - element in middle on average

Space Complexity: O(1)

• Only uses constant extra space
• No additional arrays or data structures needed

---

7. When to Use Linear Search

Best For:

• Small arrays
• Unsorted arrays
• When array is not frequently searched
• Simple implementation needed
• When data is not sorted

Not Recommended For:

• Large arrays (use Binary Search if sorted)
• Frequent searches (sort first, then use Binary Search)
• Performance-critical applications
• When array is already sorted (Binary Search is better)

---

8. Important Considerations

Works on Any Array:

• Sorted arrays: works but inefficient
• Unsorted arrays: only option (must sort first for Binary Search)
• No preprocessing required

Return Value:

• Returns index if found (0 to n-1)
• Returns -1 if not found
• Check return value before using index

Comparison Count:

• Best case: 1 comparison (element at start)
• Worst case: n comparisons (element at end or not found)
• Average case: n/2 comparisons

---

9. Advantages and Disadvantages

Advantages:

• Simple to understand and implement
• Works on unsorted arrays
• No preprocessing required
• Versatile - works on any data type

Disadvantages:

• Slow for large arrays: O(n) time
• Inefficient compared to Binary Search for sorted arrays
• Must check every element in worst case

---

10. return 0;

This ends the program successfully.

---

Summary

• Linear Search sequentially checks each element until match found or array exhausted.
• Time complexity: O(n) worst/average, O(1) best case.
• Space complexity: O(1) - only uses constant extra space.
• Works on both sorted and unsorted arrays.
• Simple algorithm - easy to understand and implement.
• Returns index if found, -1 if not found.
• Best for small arrays or unsorted data.
• Understanding Linear Search is foundation for learning efficient search algorithms.

This program is fundamental for beginners learning searching algorithms, understanding sequential access, and preparing for more efficient algorithms like Binary Search in C++ programs.