Linear Search Algorithm

Linear Search Algorithm

Linear search is a simple search algorithm used to find an element in a list. It sequentially checks each element until it finds the target element or reaches the end of the list.

How Linear Search Works

1. Start at the first element of the list.
2. Compare the target element with the current element.
3. If the target matches the current element, return the index.
4. If the target does not match, move to the next element.
5. Repeat steps 2-4 until the target is found or the list ends.

Pseudocode

Here is the pseudocode for a linear search algorithm:

BEGIN
    INPUT list, target
    FOR each element in list
        IF element == target THEN
            RETURN index
        ENDIF
    ENDFOR
    RETURN -1  // Target not found
END

Example in Python

Below is an example implementation of linear search in Python:

numbers = [4, 2, 7, 1, 3, 6]
target = 7
position = -1

for i in range(len(numbers)):
  if numbers[i]==target:
    print("Found")
    position=i


if position != -1:
    print("Element found at index" + str(position))
else:
    print("Element not found")

This can be altered to count how many times an item appears in a list also using a linear search

numbers = [4, 2, 7, 1, 3, 6]
target = 7
count =0

for i in range(len(numbers)):
  if numbers[i]==target:
    print("Found")
    count=count+1

print("Element found " + str(count) + " times")

Key Points

Use Cases: Best suited for small or unsorted lists.

Advantages

• Simple to implement.
• No need for the list to be sorted.

Disadvantages

• Inefficient for large lists.
• Slower compared to other search algorithms like binary search for large datasets.

• Time Complexity: O(n), where n is the number of elements in the list.
• Space Complexity: O(1), as it uses a constant amount of extra space.