Online Training
Q4 2024
Nov 19 to Dec 10
11.00 AM EST: USA, UK, Canada, Mexico and Europe
06.00 AM GMT: MiddleEast, Asia and Australia
Linear search can be used to find the smallest or largest value in an unsorted list. It works by comparing each value in the list to keep track of the current smallest or largest value.
Create a variable called max_value_index
Set max_value_index to the index of the first element of the list
For each element in the list
If the element is greater than the current max_value_index
Update max_value_index to the index of this element
Return max_value_index
In a list with n items, the best case for a linear search is when the target value is the first item in the list. In this case, only one comparison is needed, making the best case performance O(1).
For each element in the list
If the element is equal to the target value
Return its index
If no match is found
Return "Value Not Found" message
Linear search examines each item in the list one by one, so the maximum number of comparisons is equal to the length of the list. This gives it a complexity of O(n).
For each element in the list
If the element matches the target value
Print a success message
Return its index
If no match is found
Print "Value not found" message
Return -1
A linear search function iterates through the list to find a value, adding the index of each match to a list. It increases linearly with the size of the list.
For each element in the list
If the element matches the target value
Add its index to a list of matches
If the list of matches is empty
Raise a ValueError
Otherwise
Return the list of matches
A linear search function compares each item in the list to find a match. If found, it returns the index of the item; if not, it raises an error.
def linear_search(lst, target):
for idx in range(len(lst)):
if lst[idx] == target:
return idx
raise ValueError("{0} not in list".format(target))
recipe = ["nori", "tuna", "soy sauce", "sushi rice"]
ingredient = "avocado"
try:
print(linear_search(recipe, ingredient))
except ValueError as msg:
print("{0}".format(msg))
You can adjust a linear search function to return the highest value from a list, not just a specific target. If no match is found, it returns a message.
def find_maximum(lst):
max_value = None
for el in lst:
if max_value is None or el > max_value:
max_value = el
return max_value
test_scores = [88, 93, 75, 100, 80, 67, 71, 92, 90, 83]
print(find_maximum(test_scores)) # returns 100
A linear search can be modified to return all indices where the target value appears in the list. This allows finding multiple matches if they exist.
def linear_search(lst, target):
matches = []
for idx in range(len(lst)):
if lst[idx] == target:
matches.append(idx)
if matches:
return matches
else:
raise ValueError("{0} not in list".format(target))
scores = [55, 65, 32, 40, 55]
print(linear_search(scores, 55))
If a target value isn't found in the list during a linear search, the function will raise a ValueError. It's good practice to use try-except blocks to handle this.
def linear_search(lst, target):
for idx in range(len(lst)):
if lst[idx] == target:
return idx
raise ValueError('Sorry, {0} is not found.'.format(target))
You can use a linear search to find the maximum value in a list by comparing each value and updating the maximum as you go.
def find_maximum(lst):
max_value = lst[0]
for el in lst:
if el > max_value:
max_value = el
return max_value
nums = [10, 20, 30, 40, 50]
print(find_maximum(nums)) # returns 50
Linear search can be useful for complex problems when you need to find all occurrences of a target value in a list. It's flexible and reusable.
# Linear search finds all indices of the target value
# It doesn't stop after finding the first match
Binary search is more efficient than linear search for sorted lists. Its complexity is O(log n) because it repeatedly divides the list in half.
def binary_search(sorted_list, target):
left, right = 0, len(sorted_list) - 1
while left <= right:
mid = (left + right) // 2
if sorted_list[mid] == target:
return mid
elif sorted_list[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Binary search can be implemented iteratively using a loop. This approach avoids the overhead of recursion and can be easier to understand.
# Iterative binary search example
# The loop continues until the target is found or the search space is exhausted
In a recursive binary search, base cases handle the situation where the target is found or the search space is empty. These cases stop the recursion.
# Recursive binary search with base cases
# If target is not found or list is empty, return appropriate result
In recursive binary search, the pointers are updated based on whether the target value is less than or greater than the middle value. This helps in narrowing down the search space.
# Recursive binary search updates pointers based on comparisons
# Adjust left and right pointers accordingly
Binary search performs well on large datasets by reducing the search space logarithmically. Its performance is significantly better than linear search for sorted lists.
# Binary search performance is improved for large datasets
# Compared to linear search, it finds results faster in sorted lists
Favourites
Monitor your IT infrastructure effortlessly with Site24x7 and get comprehensive insights and ensure smooth operations with 24/7 monitoring.
Sign up now
Welcome to our comprehensive collection of programming language cheatsheets! Whether you're a seasoned developer or a beginner, these quick reference guides provide essential tips and key information for all major languages. They focus on core concepts, commands, and functions—designed to enhance your efficiency and productivity.
ManageEngine Site24x7, a leading IT monitoring and observability platform, is committed to equipping developers and IT professionals with the tools and insights needed to excel in their fields.
Monitor your IT infrastructure effortlessly with Site24x7 and get comprehensive insights and ensure smooth operations with 24/7 monitoring.
Sign up now!
Java
HTML and CSS 
Python
Javascript
Troubleshooting
Blogs
Learn
Tools