Consider the searching problem:
Input: A sequence of n numbers in array and a value
Output: An index such that equals or the special value if does not appear in .
Write a pseudocode for linear search, which scans through the array from beginning to end, looking for and using a loop invariant, proving that your algorithm is correct. make sure that your loop invariant fulfills the three necessary properties.
Linear search on Wikipedia
Pseudocode:
LINEAR-SEARCH A, n, x
for i = 1 to n
if A[i] = x
return i
return NIL
Solution in Python
def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return None
Example usage:
test_list = [5, 8, 2, 9, 3, 6] target_element = 9 index = linear_search(test_list, target_element) if index == None: print(f"Element {target_element} not found.") else: print(f"Element {target_element} found at index {index}.")
Loop Invariant:
Initialization: The loop is initialized by setting to 1 – the first index of the array. If the array is empty, the loop is not initialized.
Maintenance: The loop is maintained by increasing the value of till the end of the last element in the array .
Termination: The loop is terminated when a desired element is found or when the is greater than the length of the array.