0

I load data from a website's pages. The problem is that the ammount of pages is unkown.

Since this process takes a long time, I want to display a progress dialog. For that I have to find the last page. My idea to find the last page is:

  • Try to load page 1000
    • if page 1000 exists try to load page 2000
      • if page 2000 exists try to load page 4000
      • if page 2000 does not exist try to load page 1500
    • if page 1000 does not exist try to load page 500
      • if page 500 exists try to load page 750
      • if page 500 does not exist try to load page 250

and so on.. So simply doubling/halfing the distance between the pages.

I am stuck and failing to implement this algorithm in C#. Since searching for 'Half distance / double distance algorithm' brought up no usefull results, maybe here someone can tell me more about it.

Is there a sample implementation for this kind of problem or does this specific kind of algorithm have a name?

closed as off-topic by Doc Brown, Shog9 Sep 23 '16 at 19:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking for assistance in writing or debugging existing code are off-topic on Programmers. These questions can be asked on Stack Overflow if they include the desired behavior, a specific problem or error, and the shortest code necessary to reproduce it in the question itself. See How To Create a Minimal, Complete, and Verifiable Example." – Doc Brown, Shog9
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    How to debug small programs – Dan Pichelman Sep 19 '16 at 16:31
  • 3
  • While this doesn't answer your direct question, you could just query the size of the requested data set first, before the retrieval. Then you will know up front how many records you will be getting. – Eric King Sep 19 '16 at 17:00
  • @EricKing this is sadly not possible if I understood you correctly. I know that every page has 250 records (except the last one), but I don't konw how many pages there are. – SmallestUncomputableNumber Sep 19 '16 at 17:08
  • 2
    This is an algorithm question. He has an algorithm in mind but doesn't know it's name. It's answerable and on topic. – candied_orange Sep 19 '16 at 22:07
6

The name of the algorithm you are describing is Exponential Search, also known as doubling search or galloping search.

The Wikipedia article has a sample implementation that may be of interest.

Not the answer you're looking for? Browse other questions tagged or ask your own question.