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.