Searching Algorithms

Question 1

What is sequential search?

Answer 1

Sequential search, or linear search, is a method for finding a particular value in a list that checks each element in sequence until the desired element is found or the list is exhausted. The list need not be ordered. The best case for sequential search is that it does one comparison, and matches X right away. In the worst case, sequential search does n comparisons, and either matches the last item in the list or doesn’t match anything.

Question 2

What is binary search?

Answer 2

A binary search, or half-interval search, halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time.

Best case: O(1)
Worst case: O(log n)

Question 3

What is hashing?

Answer 3

Hashing is a type of search in which a function is used to give the index of a stored value.