Problem $1$:

Imagine you are working for a large e$-$commerce company that handles a vast inventory of products. The company needs to implement an efficient search feature to help users find products by their unique Product ID$.$ The system deals with three different data structures for storing product information:

Dataset X: A list of $100,000$ unsorted Product IDs.

Dataset Y: A list of $100,000$ sorted Product IDs.

Dataset Z: A list of $1$ million sorted Product IDs with very large gaps between consecutive Product IDs.

You need to compare the following search algorithms to determine which one would perform best for each dataset:

Sequential Search

Binary Search

Key$-$Indexed Search

For each dataset $(x,Y,$ and $Z),$ analyze the performance of the three search algorithms and determine the most efficient one. Consider factors such as asymptotic time complexity, empirical running time, asymptotic space complexity, the structure of the data, and size of the dataset in your analysis. Justify your selection of the best search algorithm for each dataset.