🔍 Linear Search and Basic Concepts

Welcome to the world of searching algorithms! Before we dive into fancy techniques, let’s start with the basics. Think of searching like looking for your keys - sometimes you just have to check everywhere!

Why Searching Matters - The “Finding Stuff” Problem

Imagine you have a phone book with millions of names. How do you find “Smith, John”? Or picture a database with customer records - how does the computer find your account instantly?

Searching is one of the most fundamental computer science problems. Every app you use - from Google to your banking app - relies on fast searching to work.

1. Linear Search - The “Check Everything” Method

Linear search is like looking for your lost phone by checking every room in your house. It’s simple, but it works!

How Linear Search Works

Find 42 in: [10, 20, 30, 42, 50, 60]

Step 1: Check position 0: 10 ≠ 42, continue Step 2: Check position 1: 20 ≠ 42, continue Step 3: Check position 2: 30 ≠ 42, continue Step 4: Check position 3: 42 = 42, FOUND!

// LinearSearch checks every element until it finds the target
func LinearSearch(arr []int, target int) int {
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            return i  // Found it! Return the position
        }
    }
    return -1  // Not found
}

Best for: Small lists, unsorted data Worst for: Big lists (slow!) Speed: O(n) - checks up to n items

Linear Search with Early Exit

Sometimes you want to find ALL matches, not just the first one:

// LinearSearchAll finds all positions where target appears
func LinearSearchAll(arr []int, target int) []int {
    var positions []int

    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            positions = append(positions, i)
        }
    }

    return positions
}

Real-World Examples - Where Linear Search Saves the Day

1. Finding Text in a Document

import "strings"

// FindWordInText searches for a word in text (like Ctrl+F)
func FindWordInText(text, word string) []int {
    var positions []int
    words := strings.Fields(text)  // Split into words

    for i, w := range words {
        if strings.EqualFold(w, word) {  // Case-insensitive match
            positions = append(positions, i)
        }
    }

    return positions
}

Used in: Word processors, code editors, web browsers

2. Checking if Item Exists in Small List

// IsItemInList checks if an item exists (faster than sorting first)
func IsItemInList(items []string, target string) bool {
    for _, item := range items {
        if item == target {
            return true
        }
    }
    return false
}

Used in: Small configuration lists, validation checks

3. Finding Maximum/Minimum in Unsorted Data

// FindMax finds the largest number (without sorting)
func FindMax(arr []int) int {
    if len(arr) == 0 {
        return 0  // Or handle error
    }

    max := arr[0]  // Start with first element
    for i := 1; i < len(arr); i++ {
        if arr[i] > max {
            max = arr[i]
        }
    }

    return max
}

Used in: Real-time data, streaming analytics

The Big O Trade-off - Time vs. Simplicity

Practice Problems - Build Your Search Skills!

1. Word Counter: Count how many times each word appears in a text
2. Find Duplicates: Find all numbers that appear more than once in a list
3. Best Score: Find the highest score in a list of student grades
4. Missing Number: Find which number from 1-100 is missing from a list

Key Takeaways - What You Learned

• Linear search checks every element - simple but slow for big data
• O(n) time means time grows with data size
• Best for small, unsorted data or when you need simplicity
• Real applications include text search, validation, and finding extremes

Next: We’ll learn Binary Search - the “divide and conquer” approach that can find things in huge datasets almost instantly! ⚡

Ready for faster searching? Let’s move to Binary Search! 🚀