Linear Search

What You’ll Learn 📚

• What is Linear Search?
• Key terminology and concepts
• Step-by-step examples from simple to complex
• Common questions and answers
• Troubleshooting common issues

Introduction to Linear Search

Linear Search is one of the simplest search algorithms. It checks each element in a list one by one until it finds the target value or reaches the end of the list. It’s like flipping through a book page by page to find a specific word. 📖

Key Terminology

• Algorithm: A step-by-step procedure for solving a problem.
• Linear Search: A search algorithm that checks each element in a list sequentially.
• Target Value: The value you’re searching for in the list.

Simple Example: Finding a Number

# Simple Linear Search in Python
def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index  # Target found, return index
    return -1  # Target not found

# Example usage
numbers = [10, 20, 30, 40, 50]
result = linear_search(numbers, 30)
print(f'Target found at index: {result}')  # Expected Output: Target found at index: 2

Progressively Complex Examples

Example 1: Linear Search with Strings

// Linear Search in JavaScript
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;  // Target found, return index
        }
    }
    return -1;  // Target not found
}

// Example usage
const fruits = ['apple', 'banana', 'cherry', 'date'];
const result = linearSearch(fruits, 'cherry');
console.log(`Target found at index: ${result}`);  // Expected Output: Target found at index: 2

Example 2: Linear Search in a Large Dataset

// Linear Search in Java
public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // Target found, return index
            }
        }
        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int result = linearSearch(numbers, 7);
        System.out.println("Target found at index: " + result);  // Expected Output: Target found at index: 6
    }
}

Common Questions and Answers

1. What is the time complexity of Linear Search?
   Linear Search has a time complexity of O(n), where n is the number of elements in the list.
2. Can Linear Search be used on unsorted lists?
   Yes, Linear Search works on both sorted and unsorted lists.
3. What happens if the target is not in the list?
   The function returns -1, indicating the target was not found.
4. Is Linear Search efficient?
   Linear Search is not the most efficient for large datasets, but it's simple and works well for small lists.

Troubleshooting Common Issues

Ensure your loop iterates over the entire list. Missing elements can lead to incorrect results.

Remember to return -1 if the target is not found. This is a common mistake!

Practice Exercises

• Modify the Python example to search for a target in a list of dictionaries.
• Implement Linear Search in a different programming language you're learning.
• Try using Linear Search to find a target in a 2D array.

Don't worry if this seems complex at first. With practice, you'll get the hang of it! 💪

Additional Resources

• Wikipedia: Linear Search
• GeeksforGeeks: Linear Search