Searching online catalogs is a pain. Can you tell me if it's worth my trouble?
As an example, I searched the following online catalog of a well-known country-wide British outlet for the keyword "puzzles". Many other suppliers use the same algorithm and I have no financial interest in any of them.
I selected Sort by price: Low-High.
My intention was to find an item or items costing as near as possible to the mean of the extremes. In this case (1.50 + 150.00)/2 = 75.75 but please answer the general question, not this specific one.
I then scrolled to the bottom of the page (!!!???), in order to see how many pages there were and to select an item in the middle of the price range.
It seems that catalog website-designers have never heard of binary search.
Such a catalog is necessarily dynamic so I won't ask about the specific case.
By experiment, can you identify the algorithm used and give a general nClicks requirement for the worst-possible case for finding the averagely* priced product, compared with that for binary search?
*Average here is defined as the mean of the extremes.
I am looking for a general answer for the specific algorithm, not for my specific search.
(1) The catalog for a given product type is divided into p pages, each containing i items. Ignore the possibility of incomplete pages.
(2) For the purpose of this problem you may ignore the actual catalog and assume that the price for each item is different from all others.
Please ask for clarifications where necessary before attempting an answer.