A sequential search of a sorted list can halt when the target is less than a given element in the list.
Define a modified version of this algorithm, and state the computational complexity, using big-O notation, of its best-, worst-, and averagecase performances.
“””
File: search.py
Defines functions for sequential search and binary search with a profiler.
“””
defsequentialSearch(target, lyst):
“””Returns the position of the target item if found,
or -1 otherwise.”””
position = 0
while position <len(lyst):
if target == lyst[position]:
return position
position += 1
return -1
def main():
“””Tests with three lists.”””
print(sequentialSearch(3, [0, 1, 2, 3, 4]))
print(sequentialSearch(3, [0, 1, 2]))
# Should stop at second position.
print(sequentialSearch(3, [0, 4, 5, 6]))
if __name__ == “__main__”:
main()
