Linear Search Algorithm

Linear Search, also known as sequential search, is the simplest searching algorithm. It checks every element in the list sequentially until the desired element is found or the list ends.

Working of Linear Search

• Start from the first element.
• Compare the current element with the target element.
• If it matches, return the index.
• If not, move to the next element and repeat.
• If the end is reached without a match, the element is not in the list.

Algorithm/Pseudocode

Pseudocode:

procedure linear_search(arr, x)
    for i = 0 to length(arr) - 1 do
        if arr[i] = x then
            return i
    return -1

Time Complexity

• Best Case: O(1) when the element is present at the first position.
• Average Case: O(n)
• Worst Case: O(n) when the element is not present or at the last position.

Python Code Example

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Usage Example
arr = [10, 23, 45, 70, 11, 15]
target = 70

result = linear_search(arr, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found in the list")

Applications

• Useful for small or unsorted data.
• Finding an element when simple and straightforward coding is needed.
• Suitable for unsorted or small arrays where implementing more complex search algorithms is unnecessary.