Linear Search

#include <iostream>
using namespace std;

void print(int arr[], int n) {
    // Print the size of the current array
    cout << "Size of array is " << n << endl;

    // Loop to print each element of the array
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

bool linearSearch(int arr[], int size, int k) {
    // Print the current array (useful for understanding recursion)
    print(arr, size);

    // Base case: if the array size is zero, the element was not found, return false
    if(size == 0)
        return false;

    // Check if the first element of the array is equal to the target 'k'
    if(arr[0] == k) {
        return true;  // Element found, return true
    }
    else {
        // Recursively call the function for the remaining part of the array (excluding the first element)
        // `arr + 1` moves the pointer to the next element, and `size - 1` reduces the size of the array
        bool remainingPart = linearSearch(arr + 1, size - 1, k);
        return remainingPart;  // Return the result of the recursive search
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr)/sizeof(arr[0]);
    int key = 3;

    if(linearSearch(arr, size, key)) {
        cout << "Element found!" << endl;
    } else {
        cout << "Element not found." << endl;
    }

    return 0;
}

Example:

Suppose we call linearSearch(arr, 5, 3) with arr[] = {1, 2, 3, 4, 5} and the target k = 3:

• First Call:
  • arr[] = {1, 2, 3, 4, 5}, size = 5
  • arr[0] = 1, which is not equal to 3, so it calls linearSearch(arr + 1, 4, 3).
• Second Call:
  • arr[] = {2, 3, 4, 5}, size = 4
  • arr[0] = 2, which is not equal to 3, so it calls linearSearch(arr + 1, 3, 3).
• Third Call:
  • arr[] = {3, 4, 5}, size = 3
  • arr[0] = 3, which is equal to 3, so it returns true.

Output:

Size of array is 5
1 2 3 4 5
Size of array is 4
2 3 4 5
Size of array is 3
3 4 5
Element found!