Linear Search

  • Linear search is a basic search algorithm that sequentially checks each element in a list until the target element is found or the list is exhausted.
  • It resembles how you might search for a specific word in a physical book by flipping through pages one by one.
def linear_search(list1, x):
  """
  Performs linear search on a given list to find the specified element.

  Args:
    list1: The list to search through.
    x: The element to search for.

  Returns:
    The index of the element if found, otherwise -1.
  """

  for i in range(len(list1)):  # Iterate through each element's index
    if list1[i] == x:  # Check if the current element matches the target
      return i  # Element found, return its index

  return -1  # Element not found in the list
  • Time Complexity:
    • Linear search has a time complexity of O(n), meaning its execution time grows linearly with the size of the list n. In the worst-case scenario, it might need to check every element before finding (or not finding) the target.
     
  • Suitability:
    • Linear search is simple to implement, but it might not be the most efficient choice for large lists.
    • It’s generally suitable for:
      • Small lists
      • Unsorted data where sorting isn’t feasible or necessary
      • Cases where simplicity is prioritize over speed.
  • Alternatives for Large Lists:
    • For larger lists, consider more efficient algorithms like binary search, which has a time complexity of O(log n), but requires the list to be sorted.