Linear Search

9.2 Linear Search

Linear Search, also known as Sequential Search, is the most straightforward searching algorithm. It works by sequentially checking each element in a list until the desired element is found or the end of the list is reached.

How Linear Search Works

The process of linear search involves the following steps:

1. Start at the beginning: Begin by examining the first element of the list.

2. Compare: Compare the current element with the target value you are searching for.

3. Match found: If the current element matches the target value, the search is successful. The index of this element is returned.

4. No match: If the current element does not match the target value, move to the next element in the list and repeat the comparison.

5. End of list reached: If the end of the list is reached without finding a match, it means the target element is not present in the list. In this case, a special value (commonly -1) is returned to indicate that the element was not found.

Python Implementation of Linear Search

Function to Perform Linear Search

def linear_search(arr, target):
    """
    Performs a linear search on a list to find the index of a target element.

    Args:
        arr (list): The list to search within.
        target: The element to search for.

    Returns:
        int: The index of the target element if found, otherwise -1.
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return index if target is found
    return -1  # Return -1 if target is not found

Example Usage

## Example list
my_list = [12, 45, 78, 34, 89, 23]
## Target element to find
search_target = 78

## Perform linear search
found_index = linear_search(my_list, search_target)

## Display the result
if found_index != -1:
    print(f"Element {search_target} found at index {found_index}")
else:
    print(f"Element {search_target} not found in the list.")

## Example for an element not in the list
another_target = 50
not_found_index = linear_search(my_list, another_target)

if not_found_index != -1:
    print(f"Element {another_target} found at index {not_found_index}")
else:
    print(f"Element {another_target} not found in the list.")

Output:

Element 78 found at index 2
Element 50 not found in the list.

Time and Space Complexity

| Complexity Type | Value | Description | | :-------------- | :---- | :-------------------------------------------------------------------------- | | Best Case | O(1) | Occurs when the target element is the first element in the list. | | Average Case | O(n) | Occurs when the target element is somewhere in the middle of the list. | | Worst Case | O(n) | Occurs when the target element is the last element or is not present. | | Space Complexity| O(1) | Linear search requires a constant amount of extra space, regardless of input size. |

Here, 'n' represents the number of elements in the list.

When to Use Linear Search

Linear search is a suitable choice in the following scenarios:

• Unsorted Data: When the data you are searching through is not sorted or ordered.

• Small Datasets: For lists or arrays that contain a small number of elements, the inefficiency of linear search is negligible.

• Simplicity is Key: When ease of implementation and understanding is prioritized over absolute performance.

• Data Structures without Direct Access: It is useful for data structures where direct access to elements by index is not efficient or possible, such as linked lists.

Key Features of Linear Search

• Versatility: It can operate on both sorted and unsorted data.

• Simplicity: Its straightforward logic makes it easy to implement and understand, making it a good starting point for learning search algorithms.

• Efficiency for Small Data: While not efficient for large datasets, it performs adequately for smaller ones.

• Foundation: It serves as a foundational algorithm, providing a basis for understanding more advanced searching techniques like Binary Search.

Linear search is a fundamental algorithm in computer science, ideal for beginners and for tackling problems where high performance is not a critical requirement. It effectively demonstrates the core concept of searching through data.

Interview Questions

• What is linear search and how does it work in Python?

• What is the time complexity of linear search?

• In which scenarios is linear search more suitable than binary search?

• How would you implement linear search in Python?

• What are the advantages and disadvantages of linear search?

• Can linear search be used on unsorted data? Why?

• What is the space complexity of linear search?

• How would you perform linear search on a linked list in Python?

• How does linear search handle duplicate elements?

• What changes would you make to return all indices of the target element in linear search?