Exercise 2.1-4

Exercise 2.1-4

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.