Searching

Question 1

Unordered Linear Search

Answer 1

The data is not ordered so the complete array must be scanned to find an element. Time complexity is O(n) in the worst case when we need to scan the complete array.

Question 2

Sorted/Ordered Linear Search

Answer 2

The data is ordered so once an element is found to be greater than the data to be searched, the search is over. Time complexity is O(n) because if the entire array is filled with elements smaller than he search data, the whole array must be searched.

Question 3

Binary Search

Answer 3

The ordered data set is divided in half and the midpoint is compared to the search data. If it is less than the midpoint, the same processes is carried out with the first half. If it is greater than the midpoint, the same process is carried out for the second half. This continues until the left datapoint and the right datapoint meet. Time complexity is O(logn).

Question 4

Interpolation Search

Answer 4

An iteration of binary search, but it uses a better guess for the midpoint using assumptions. Time complexity for average case is O(log(logn)).