Algorithms for searching

Question 1

Explain the steps taken to perform a linear search, using a worked example as part of your explanation.

Answer 1

Linear search involves checking every element in a list in order, one-by-one until the desired element is found.

Question 2

Explain the steps taken to perform a binary search,

Answer 2

Binary search operates on a sorted list, choosing the middle element and comparing it with the target. If they match, the search ends. If not, it narrows the search to the left or right, repeating until the item is found or no more elements remain.

Question 3

Roland performs both linear and binary searches on a large dataset for the same item. Surprisingly, the linear search proves much faster than the binary search. How is this discrepancy possible?

Answer 3

Binary search is generally more efficient in average and worst-case scenarios compared to linear search.

However, if the item is at the beginning of the list, linear search outperforms binary search. For instance, in a list of 1000 items, linear search checks 1 item, while binary search checks at most 10, thanks to its ability to halve the search space with each comparison.