`Video Explanation: Linear Search - CS50 Shorts`

Definition

Linear Search is a fundamental search algorithm that locates the position of a target element by sequentially traversing each item in a collection, such as an array or linked list, one by one until a match is found or the end is reached. It requires no sorting, works on many sequentially traversable collections, and prioritizes simplicity over efficiency.

✅ Advantages	❌ Disadvantages
Easy to understand and implement	Can be inefficient for large datasets
Works with both sorted and unsorted data	Slower than Binary Search on sorted arrays
Works on arrays, linked lists, etc.	O(n) time in worst case (linear time complexity)

Example

Start at the first element of the list.
Compare the current element with the target.
If they match, return the index.
If not, move to the next element.
Repeat until the element is found or the list ends.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // Found it!
    }
  }

  return -1; // Not found
}

def linear_search(arr: list[int], target: int) -> int:
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Found it!

    return -1  # Not found

class Solution {
    public int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Found it!
            }
        }

        return -1; // Not found
    }
}

#include<vector>
using namespace std;

class Solution {
public:
    int linearSearch(const vector<int>& arr, int target) {
        for (int i = 0; i < static_cast<int>(arr.size()); i++) {
            if (arr[i] == target) {
                return i; // Found it!
            }
        }

        return -1; // Not found
    }
};

int linearSearch(const int arr[], int length, int target) {
    for (int i = 0; i < length; i++) {
        if (arr[i] == target) {
            return i; // Found it!
        }
    }

    return -1; // Not found
}

function linearSearch(arr: number[], target: number): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // Found it!
    }
  }

  return -1; // Not found
}

fun linearSearch(arr: IntArray, target: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == target) {
            return i // Found it!
        }
    }

    return -1 // Not found
}

func linearSearch(_ arr: [Int], _ target: Int) -> Int {
    for i in 0..<arr.count {
        if arr[i] == target {
            return i // Found it!
        }
    }

    return -1 // Not found
}

public class Solution
{
    public int LinearSearch(int[] arr, int target)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] == target)
            {
                return i; // Found it!
            }
        }

        return -1; // Not found
    }
}

func linearSearch(arr []int, target int) int {
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            return i // Found it!
        }
    }

    return -1 // Not found
}

Time & Space Complexity

Case	Time Complexity	Explanation
Best Case	O(1)	Target is the first element
Average	O(n)	On average, it may check half the list which simplifies to O(n)
Worst Case	O(n)	Target is at the end or not present
Space	O(1)	No extra space needed

Linear Search vs Binary Search

Feature	Linear/Sequential Search	Binary Search
Data Requirement	Unsorted or Sorted	Sorted only
Time (Best / Worst)	O(1) / O(n)	O(1) / O(log n)
Use Case	Small or Unsorted Collections	Large, Sorted Collections
Space Complexity	O(1)	O(1)
Implementation Simplicity	✅ Easy	❌ Needs careful handling

Use Cases

Real Life	Description
Finding a book on a messy shelf	Check each book one by one until the target is found
Searching for your car in a parking lot	Walk row by row until you locate your car
Checking names in an attendance sheet	Go line by line until the name is matched
Finding a file in a folder	Open and check each file sequentially

Computer Science	Field	Description
Matching a word/token in a sentence	NLP	Check each token one by one until the target token is found
Linear scan in data pipelines	Data Science	Perform simple checks across unstructured datasets
Searching logs for anomalies	Cybersecurity	Sequential scan to detect patterns or threats
Finding a value in an unindexed list	Machine Learning	Lookup values one by one in non-indexed structures

Core Algorithmic	Description
Search in Unsorted Array	When data is unordered and you must find the position of a target value
First / Last Occurrence	Find the index of the first / last time a value appears
Search in Linked List	Linked lists need node-by-node traversal
Pattern Checking	Check for substring/pattern in raw string
Search in Range/Subarray	Target may only appear within a specific range of indices