Searching Algorithms

Question 1

What is sequential/linear search? and what are its advantages and disadvantages? and what is its time and space complexity?

Answer 1

It is a search algorithm where every element in a list is traversed until the desired element is found.

Advantages:
-It is easy to implement
-It does not require a sorted list

Disadvantages:
-It is inefficient for large data sets

Time complexity = O(n)
space complexity = O(1)

Question 2

What is binary/dichotomy search? and what are its advantages and disadvantages? and what is its time and space complexity?

Answer 2

It is a search algorithm that requires a sorted list and divides the number of required traversals by 2.

Advantages:
It is efficient for large data sets

Disadvantages:
It requires a sorted list
Insertion and deletion are very costly

Time complexity = O(log n)
Space complexity = O(1)