Question

If an element is present in an array of length n, how many element visits, on average, are necessary to find it using a linear search

Answer 1

Answer:

n/2

Explanation:

A linear search starts at the beggining of the array at index 0 and searches for the specific element by analyzing one element at a time. Meaning that if it does not exist in index 0 it moves to index 1 and if its not there it moves to index 2 and so on. If the element is not present in the array it finishes the array and ends, otherwise if it finds the element the search automatically ends. This means that on average the search would end early half of the time. This would mean that on average a total of n/2 elements are visited using a linear search.