Linear Search¶

Definition¶

The simplest search algorithm that checks each element sequentially from the beginning until the target is found or the end of the collection is reached. Also known as Sequential Search.

Key Insight: Works on ANY collection - unsorted, linked list, etc.

Big O Complexity¶

When to Use¶

Pros and Cons¶

Implementation¶

Basic Linear Search¶

public 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
}

With Sentinel (Optimization)¶

// Eliminates bounds check in each iteration
public int linearSearchSentinel(int[] arr, int target) {
    int n = arr.length;
    if (n == 0) return -1;

    int last = arr[n - 1];

    // Place target as sentinel at end
    arr[n - 1] = target;

    int i = 0;
    while (arr[i] != target) {
        i++;
    }

    // Restore original value
    arr[n - 1] = last;

    // Check if found before sentinel
    if (i < n - 1 || arr[n - 1] == target) {
        return i;
    }
    return -1;
}

Recursive Linear Search¶

public int linearSearchRecursive(int[] arr, int target, int index) {
    if (index >= arr.length) return -1;
    if (arr[index] == target) return index;
    return linearSearchRecursive(arr, target, index + 1);
}

Find All Occurrences¶

public List<Integer> findAllOccurrences(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;
}

Generic Linear Search¶

public <T> int linearSearch(T[] arr, T target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i].equals(target)) {
            return i;
        }
    }
    return -1;
}

// With predicate
public <T> int linearSearch(T[] arr, Predicate<T> condition) {
    for (int i = 0; i < arr.length; i++) {
        if (condition.test(arr[i])) {
            return i;
        }
    }
    return -1;
}

Linear Search in Linked List¶

public ListNode search(ListNode head, int target) {
    ListNode current = head;

    while (current != null) {
        if (current.val == target) {
            return current;
        }
        current = current.next;
    }

    return null;
}

Bidirectional Linear Search¶

// Search from both ends - reduces iterations by half on average
public int linearSearchBidirectional(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        if (arr[left] == target) return left;
        if (arr[right] == target) return right;
        left++;
        right--;
    }

    return -1;
}

Variations¶

Find Minimum/Maximum¶

public int findMin(int[] arr) {
    if (arr.length == 0) throw new IllegalArgumentException();

    int min = arr[0];
    int minIndex = 0;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
            minIndex = i;
        }
    }

    return minIndex;
}

public int findMax(int[] arr) {
    if (arr.length == 0) throw new IllegalArgumentException();

    int max = arr[0];
    int maxIndex = 0;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
            maxIndex = i;
        }
    }

    return maxIndex;
}

Find First/Last Occurrence¶

public int findFirst(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

public int findLast(int[] arr, int target) {
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Count Occurrences¶

public int countOccurrences(int[] arr, int target) {
    int count = 0;
    for (int num : arr) {
        if (num == target) count++;
    }
    return count;
}

Search in 2D Array¶

public int[] linearSearch2D(int[][] matrix, int target) {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{-1, -1};
}

Search by Condition¶

// Find first element satisfying condition
public Integer findFirst(int[] arr, IntPredicate condition) {
    for (int num : arr) {
        if (condition.test(num)) {
            return num;
        }
    }
    return null;
}

// Example usage
Integer firstEven = findFirst(arr, x -> x % 2 == 0);
Integer firstNegative = findFirst(arr, x -> x < 0);

Common Patterns¶

Two Sum (Brute Force)¶

// O(n²) - linear search for complement
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{-1, -1};
}

Find Missing Number¶

// Linear search approach
public int findMissing(int[] arr, int n) {
    for (int i = 1; i <= n; i++) {
        boolean found = false;
        for (int num : arr) {
            if (num == i) {
                found = true;
                break;
            }
        }
        if (!found) return i;
    }
    return -1;
}

Find Peak Element¶

// O(n) linear scan
public int findPeakLinear(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            return i;
        }
    }
    return nums.length - 1;
}