Data Structures and Algorithms

Question 1

What is the Jump Search algorithm?

Answer 1

A search algorithm for sorted arrays that makes jumps of size k (1 <= k < n) to find which block (of size k) the element being searched for would potentially exist in. Then a linear search is done through that block for the element.

Question 2

What is the Time Complexity of the Jump Search algorithm?

Answer 2

O(sqrt(n))

Question 3

What is the optimal “jump size” (or k) in the Jump Search algorithm?

Answer 3

sqrt(n)

Question 4

What primary advantage does Jump Search have over Binary Search?

Answer 4

You only have to jump back one time.

Question 5

What is the Linear Search algorithm?

Answer 5

A search algorithm for any array that checks each element individually. Usually from left to right.

Question 6

What is the Time Complexity of the Linear Search algorithm?

Answer 6

O(n)

Question 7

What are the two classes of search algorithms?

Answer 7

Sequential - each element is checked once.

Interval - subsets of the elements are checked leveraging the fact that the collection is sorted.

Question 8

What is the Binary Search algorithm?

Answer 8

A search algorithm for sorted arrays that recursively checks a middle value and then decides which half of the interval to search by comparing that middle value with the search term.

Question 9

What is the Time Complexity of the Binary Search algorithm?

Answer 9

O(log(n))

Question 10

What is the Interpolation Search algorithm?

Answer 10

A modification of binary search that uses linear interpolation to use the midpoint.

Question 11

In what scenario is Interpolation Search advantageous over Binary Search?

Answer 11

In data sets that are relatively uniformly distributed.

Question 12

What is the position formula for Interpolation Search?

Answer 12

m = L + [(x - A[L]) * (R - L) / (A[R] - A[L])]

m = midpoint
L = left interval bound
R = right interval bound
A = the array being searched
x = the search term