Array of undefinite length..

Question

how to find a random element in a sorted array of unknown length.

Answer 1

I suppose that you have something that you can loop, but you can't determine the length beforehand. You can get a random item by looping the items, and calculate the probability that the item should be picked.

C# example to pick an int (selected) from an IEnumerable<int> (items):

Random rnd = new Random();
int cnt = 0;
int selected = 0;
foreach (int item in items) {
  if (rnd.Next(++cnt) == 0) {
    selected = item;
  }
}

At the first item, you get a random number between 0 and 0, which of course is 0, so you keep that item. At the second item, you get a random number between 0 and 1, and if it is 0, you keep the second item instead. And so on until you run out of items. For each additional item, the probability to keep that one instead gets lower, which is why the probability to end up with any specific item in the collection is the same.

Answer 2

I'll assume you mean how do I find if an element is part of the array? not how do I return a random element from the array?.

Use binary search and assume that the length is very big (surely you have an upper bound?). If the middle element m you select at each step is outside the array bounds (you need a way to tell this), then limit the search to those elements with indexes small than m.

If you don't have a way to tell if an element is outside the bounds of the array then I don't see how you could solve this.