Linear Search Algorithm

1. Algorithm Explanation

Linear search (also called sequential search) is the simplest search algorithm. Given a list of n elements and a target value T, it checks each element in order, from the first to the last, until it finds T or reaches the end of the list.

1.1 Pseudocode

function linearSearch(array A, integer n, value T):
    for i = 0 to n - 1:
        if A[i] == T:
            return i      // found at index i
    return -1             // not found
    

1.2 Time Complexity

• Best case: O(1) (target at first position)
• Average case: O(n) (target roughly in the middle)
• Worst case: O(n) (target at the end or not present)

1.3 Space Complexity

In-place algorithm using only a few extra variables: O(1).

2. Easy Problems

2.1 Problem 1: Check if Target Exists in Array

Given an integer array and a target value, return true if the target exists, otherwise false.

#include <iostream>
#include <vector>
using namespace std;

bool exists(const vector<int>& A, int T) {
    for (int x : A) {
        if (x == T) return true;
    }
    return false;
}

int main() {
    vector<int> A = {1, 3, 5, 7, 9};
    cout << (exists(A, 5) ? "Found" : "Not Found") << endl;
    return 0;
}
    

2.2 Problem 2: Find Maximum Value in Array

Given an integer array, return the maximum element.

#include <iostream>
#include <vector>
using namespace std;

int findMax(const vector<int>& A) {
    if (A.empty()) throw runtime_error("Empty array");
    int mx = A[0];
    for (int x : A) {
        if (x > mx) mx = x;
    }
    return mx;
}

int main() {
    vector<int> A = {2, 8, 4, 1, 6};
    cout << "Max = " << findMax(A) << endl;
    return 0;
}
    

3. Intermediate Problems

3.1 Problem 1: Search in a Singly Linked List

Given the head of a singly linked list and a value, return the node index (0-based) if found, else -1.

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v): val(v), next(nullptr) {}
};

int searchList(Node* head, int T) {
    int idx = 0;
    for (Node* cur = head; cur; cur = cur->next, ++idx) {
        if (cur->val == T) return idx;
    }
    return -1;
}

int main() {
    // Build list: 10 → 20 → 30 → nullptr
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(30);

    cout << searchList(head, 20) << endl;  // prints 1
    return 0;
}
    

3.2 Problem 2: First Non-Repeating Character in a String

Given a string s, find the first character that does not repeat. Use linear search to check each character’s count by scanning the string.

#include <iostream>
#include <string>
using namespace std;

char firstUnique(const string& s) {
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        bool unique = true;
        for (int j = 0; j < n; ++j) {
            if (i != j && s[j] == s[i]) {
                unique = false;
                break;
            }
        }
        if (unique) return s[i];
    }
    return '#';  // indicates none found
}

int main() {
    cout << firstUnique("swiss") << endl;  // prints 'w'
    return 0;
}
    

4. Hard Problem

4.1 Problem: Two-Sum (Naïve Approach)

Given an unsorted array and target T, return indices of the two numbers such that they add up to T. Brute-force uses nested linear searches.

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

pair<int,int> twoSum(const vector<int>& A, int T) {
    int n = A.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (A[i] + A[j] == T) {
                return make_pair(i, j);
            }
        }
    }
    return make_pair(-1, -1);  // no solution
}

int main() {
    vector<int> A = {2, 7, 11, 15};
    auto res = twoSum(A, 9);
    cout << res.first << ", " << res.second << endl;  // prints "0, 1"
    return 0;
}