Question 3: Self-Organizing Lists and caching [10]

Suppose we decide to create a searchable data structure to hold a collection of N integer data values, where the data structure has the following properties:

• The collection of N items will be arranged by frequency of use: the most frequently used items will move to the "front", while less frequently used items will move to the "back".

• In addition to the main collection, we will maintain an additional cache of K items, which will contain copies of the K most recently used items.

• Both the cache and the collection itself will be stored in arrays, named Cache and Data, and assume we know the values of N and K in advance.

Write a search routine that will look for an item (in the cache and/or main collection, as appropriate) which has data value v. Clearly state any assumptions you need to make.