Cacher is the code snippet organizer for pro developers

The linear search, or sequential search, algorithm sequentially checks whether a given value is an element of a specified list by scanning the elements of a list one-by-one. It checks every item in the list in order from the beginning to end until it finds a target value.

If it finds the target value in the list, the linear search algorithm stops and returns the position in the list corresponding to the target value. If it does not find the value, the linear search algorithm returns a message stating that the target value is not in the list.

Linear search can be used to search for a desired value in a list. It achieves this by examining each of the elements and comparing it with the search element starting with the first element to the last element in the list until it finds a match.

The steps are:

• Examine the first element of the list.
• If the first element is equal to the target value, stop.
• If the first element is not equal to the target value, check the next element in the list.
• Continue steps 1-3 until the element is found or the end of the list is reached.

Linear search is not considered the most efficient search algorithm, especially for lists of large magnitudes. However, linear search is a great choice if you expect to find the target value at the beginning of the list, or if you have a small list.

The best case performance for linear search occurs when the target value exists in the list and is in the first position of the list. In this case, the linear search algorithm will only be required to make one comparison. The time complexity for linear search in its best case is O(1).

There are two worst cases for linear search.

Case 1: when the target value at the end of the list. Case 2: when the target value does not exist in the list.

In both cases, the linear search algorithm is required to scan the entire list of N elements and, therefore, makes N comparisons.

For this reason, the time complexity for linear search in its worst case is O(N).

If this search was used 1000 times on a 1000 different lists, some of them would be the best case, some the worst. For most searches, it would be somewhere in between.

On average it would be in the middle of the list, that search would take N⁄2 time. Each element of the list on the right requires a different number of comparisons to be located in a list. Using linear search, the first element is located with one comparison, the second element is located with two comparisons, and so on until the last element is located in N, the size of the list, comparisons.

The average case performance is the average number of comparisons. To calculate this, you use this formula:

sum of # of comparisons for each element / # of elements in the list

Therefore, the average case performance for linear search is: n / 2

We would expect on average for the linear search algorithm to search halfway through the list. Therefore the time complexity for linear search in its average case is O ( N⁄2 ).

Based on Big O simplification rules, which you can learn about in the Big O lesson, we simplify the time complexity in this case to O(N).

Linear search runs in linear time. Its efficiency can be expressed as a linear function, with the number of comparisons to find a target increasing linearly as the size of the list, N, increases.

The time complexity for linear search in Big-O notation is O(N).

A time complexity of O(N) means the number of comparisons is proportional to the number of elements, N, in the list. With a list with twice as many elements, linear search will take at most take twice as long to perform the search. The time complexity of linear search is also dependent on the best case, worst case, and average case scenarios.

If a match is found, the linear search function will return the index of the matching element. Otherwise, the function will raise a ValueError, a special error to indicate that the value was not found.

# Pseudocode for linear search as a function:

# For each element in the search_list
    # if element equal target value then
       # return its index
# if element is not found then 
    # raise a ValueError

# Example of function to find one value
number_list = [ 10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
target_number = 100

def linear_search(search_list, target_value):
  for idx in range(len(search_list)):
    if search_list[idx] == target_value:
      return idx
  raise ValueError("{0} not in list".format(target_value))

try:
  # Call the function below...
  result = linear_search(number_list, target_number)
  print(result)
except ValueError as error_message:
  print("{0}".format(error_message))

-------------------------------------------------------------------------------------------------------------

# Pseudocode to find each element in a list

# For each element in the searchList
    # if element equal target value then
        # Add its index to a list of occurrences
# if the list of occurrences is empty
   # raise ValueError
# otherwise
   # return the list occurrences

# Example of linear search algorithm that finds duplicates

# Search list and target value
tour_locations = [ "New York City", "Los Angeles", "Bangkok", "Istanbul", "London", "New York City", "Toronto"]
target_city = "New York City"

#Linear Search Algorithm
def linear_search(search_list, target_value):
  matches = []
  for idx in range(len(search_list)):
    if search_list[idx] == target_value:
      matches.append(idx)
  if matches:
    return matches
  else:
    raise ValueError("{0} not in list".format(target_value))

#Function call
tour_stops = linear_search(tour_locations, target_city)
print(tour_stops)

-------------------------------------------------------------------------------------------------------------

# Pseudocode to find the maximum element

# Create a variable called max_value_index    
# Set max_value_index to the index of the first element of the search list
     # For each element in the search list
          # if element is greater than the element at max_value_index
               # Set max_value_index equal to the index of the element
# return max_value_index

# Implementation of maximum element linear search algorithm
# Search list
test_scores = [88, 93, 75, 100, 80, 67, 71, 92, 90, 83]

#Linear Search Algorithm
def linear_search(search_list):
  maximum_score_index = None
  for idx in range(len(search_list)):
    print(search_list[idx])
    if maximum_score_index ==  None or search_list[idx] > search_list[maximum_score_index]:
      maximum_score_index = idx
  return maximum_score_index 

# Function call
highest_score = linear_search(test_scores)

#Prints out the highest score in the list
print(highest_score)