Master Linear Search - O(n) Algorithm

function linearSearch(arr, target) {
    /**
     * Linear Search - Find first occurrence of target
     * Time: O(n) worst case, O(1) best case
     * Space: O(1) - no extra storage
     */
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Found at index i
        }
    }
    return -1; // Not found
}


function linearSearchAll(arr, target) {
    /**
     * Find all occurrences of target in array
     * Time: O(n) - must check all elements
     * Space: O(k) where k = number of matches
     */
    const indices = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            indices.push(i);
        }
    }
    return indices;
}


function linearSearchLast(arr, target) {
    /**
     * Find last occurrence of target
     * Time: O(n) - must scan entire array
     * Space: O(1)
     */
    let lastIndex = -1;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            lastIndex = i;
        }
    }
    return lastIndex;
}


// Usage examples
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(linearSearch(arr, 22));      // Output: 4
console.log(linearSearch(arr, 99));      // Output: -1 (not found)

// Find all occurrences
const arr2 = [5, 2, 8, 2, 9, 2];
console.log(linearSearchAll(arr2, 2));   // Output: [1, 3, 5]

// Find last occurrence
console.log(linearSearchLast(arr2, 2));  // Output: 5

package main

import "fmt"

// LinearSearch finds first occurrence of target
// Time: O(n) worst case, O(1) best case
// Space: O(1) - no extra storage
func LinearSearch(arr []int, target int) int {
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            return i // Found at index i
        }
    }
    return -1 // Not found
}

// LinearSearchAll finds all occurrences of target
// Time: O(n) - must check all elements
// Space: O(k) where k = number of matches
func LinearSearchAll(arr []int, target int) []int {
    indices := []int{}
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            indices = append(indices, i)
        }
    }
    return indices
}

// LinearSearchLast finds last occurrence of target
// Time: O(n) - must scan entire array
// Space: O(1)
func LinearSearchLast(arr []int, target int) int {
    lastIndex := -1
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            lastIndex = i
        }
    }
    return lastIndex
}

func main() {
    // Usage examples
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println(LinearSearch(arr, 22))      // Output: 4
    fmt.Println(LinearSearch(arr, 99))      // Output: -1

    // Find all occurrences
    arr2 := []int{5, 2, 8, 2, 9, 2}
    fmt.Println(LinearSearchAll(arr2, 2))   // Output: [1 3 5]

    // Find last occurrence
    fmt.Println(LinearSearchLast(arr2, 2))  // Output: 5
}

import java.util.*;

public class LinearSearch {
    /**
     * Linear Search - Find first occurrence of target
     * Time: O(n) worst case, O(1) best case
     * Space: O(1) - no extra storage
     */
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Found at index i
            }
        }
        return -1; // Not found
    }

    /**
     * Find all occurrences of target in array
     * Time: O(n) - must check all elements
     * Space: O(k) where k = number of matches
     */
    public static List<Integer> linearSearchAll(int[] arr, int target) {
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                indices.add(i);
            }
        }
        return indices;
    }

    /**
     * Find last occurrence of target
     * Time: O(n) - must scan entire array
     * Space: O(1)
     */
    public static int linearSearchLast(int[] arr, int target) {
        int lastIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                lastIndex = i;
            }
        }
        return lastIndex;
    }

    public static void main(String[] args) {
        // Usage examples
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println(linearSearch(arr, 22));      // Output: 4
        System.out.println(linearSearch(arr, 99));      // Output: -1

        // Find all occurrences
        int[] arr2 = {5, 2, 8, 2, 9, 2};
        System.out.println(linearSearchAll(arr2, 2));   // Output: [1, 3, 5]

        // Find last occurrence
        System.out.println(linearSearchLast(arr2, 2));  // Output: 5
    }
}

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

/**
 * Linear Search - Find first occurrence of target
 * Time: O(n) worst case, O(1) best case
 * Space: O(1) - no extra storage
 */
int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i; // Found at index i
        }
    }
    return -1; // Not found
}

/**
 * Find all occurrences of target in array
 * Time: O(n) - must check all elements
 * Space: O(k) where k = number of matches
 */
vector<int> linearSearchAll(const vector<int>& arr, int target) {
    vector<int> indices;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            indices.push_back(i);
        }
    }
    return indices;
}

/**
 * Find last occurrence of target
 * Time: O(n) - must scan entire array
 * Space: O(1)
 */
int linearSearchLast(const vector<int>& arr, int target) {
    int lastIndex = -1;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            lastIndex = i;
        }
    }
    return lastIndex;
}

int main() {
    // Usage examples
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    cout << linearSearch(arr, 22) << endl;      // Output: 4
    cout << linearSearch(arr, 99) << endl;      // Output: -1

    // Find all occurrences
    vector<int> arr2 = {5, 2, 8, 2, 9, 2};
    vector<int> result = linearSearchAll(arr2, 2);
    // Output: [1, 3, 5]

    // Find last occurrence
    cout << linearSearchLast(arr2, 2) << endl;  // Output: 5

    return 0;
}