Learn Data Structures and Algorithms with Python: Brute Force Algorithms Cheatsheet | Codecademy (2024)

Linear search can be used to search for the smallest or largest value in an unsorted list rather than searching for a match. It can do so by keeping track of the largest (or smallest) value and updating as necessary as the algorithm iterates through the dataset.

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 elementreturn max_value_index

Linear search runs in linear time and makes a maximum of n comparisons, where n is the length of the list. Hence, the computational complexity for linear search is O(N).

The running time increases, at most, linearly with the size of the items present in the list.

A linear search can be expressed as a function that compares each item of the passed dataset with the target value until a match is found.

The given pseudocode block demonstrates a function that performs a linear search. The relevant index is returned if the target is found and -1 with a message that a value is not found if it is not.

For each element in the array if element equal target value then return its index if element is not found, return “Value Not Found” message

A function that performs a linear search can return a message of success and the index of the matched value if the search can successfully match the target with an element of the dataset. In the event of a failure, a message as well as -1 is returned as well.

For each element in the array if element equal target value then print success message return its index if element is not found print Value not found message return -1

A linear search can be modified so that all instances in which the target is found are returned. This change can be made by not ‘breaking’ when a match is found.

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

Linear search sequentially checks each element of a given list for the target value until a match is found. If no match is found, a linear search would perform the search on all of the items in the list.

For instance, if there are n number of items in a list, and the target value resides in the n-5th position, a linear search will check n-5 items total.

def linear_search(lst, match):
 for idx in range(len(lst)):
 if lst[idx] == match:
 return idx
 else:
 raise ValueError("{0} not in list".format(match))
recipe = ["nori", "tuna", "soy sauce", "sushi rice"]
ingredient = "avocado"
try:
 print(linear_search(recipe, ingredient))
except ValueError as msg:
 print("{0}".format(msg))

def find_maximum(lst):
 max = None
 for el in lst:
 if max == None or el > max:
 max = el
 return max
test_scores = [88, 93, 75, 100, 80, 67, 71, 92, 90, 83]
print(find_maximum(test_scores)) # returns 100

def linear_search(lst, match):
 matches = []
 for idx in range(len(lst)):
 if lst[idx] == match:
 matches.append(idx)
 if matches:
 return matches
 else:
 raise ValueError("{0} not in list".format(match))
scores = [55, 65, 32, 40, 55]
print(linear_search(scores, 55))

A Linear Search function accepts two parameters:

1) input list to search from2) target element to search for in the input list

If the target element is found in the list, the function returns the element index. If it is not found, the function raises an error. When implementing in Python, use the raise keyword with ValueError().

def linear_search(lst, match):
 for idx in range(len(lst)):
 if lst[idx] == match:
 return idx
 raise ValueError('Sorry, {0} is not found.'.format(match))

• A brute force algorithm solves a problem through exhaustion: it goes through all possible choices until a solution is found.
• The time complexity of a brute force algorithm is often proportional to the input size.
• Brute force algorithms are simple and consistent, but very slow.

# pseudocode that prints all divisors of n by brute force
define printDivisors, n
 for all numbers from 1 to n
 if the number is a divisor of n
 print the number