LinearSearch

Linear Search

Problem Description

Implement a linear search algorithm that finds the position of a target value within an array.

What is Linear Search?

Linear search is the simplest searching algorithm that checks every element in the array sequentially until the target element is found or the end of the array is reached.

Characteristics

• Time Complexity: O(n) - where n is the number of elements
• Space Complexity: O(1) - no extra space needed
• Best for: Small datasets or unsorted arrays

How It Works

1. Start from the first element
2. Compare each element with the target
3. If a match is found, return the index
4. If no match is found after checking all elements, return -1

Your Task

Implement the following methods in LinearSearch.java:

1. search(int[] arr, int target) - Search for an integer in an array
2. search(String[] arr, String target) - Search for a string in an array

Test Cases to Consider

• Empty array
• Target at the beginning
• Target at the end
• Target in the middle
• Target not in array
• Array with duplicates (return first occurrence)

Hints

• Think about what to return when the array is empty
• Remember to check array bounds
• Consider using a simple for loop
• What happens if the array is null?

Follow-up Questions

1. How would you modify this to find all occurrences of the target?
2. Can you optimize this for sorted arrays? (Hint: What other search algorithm would be better?)
3. How would you handle null values in the array?

Related Algorithms

• Binary Search (for sorted arrays)
• Jump Search
• Interpolation Search