0

Consider that I have an array of sorted numbers with 0 to N-1 offset where N is the lenght of the array. A completely sorted array has 0 zero offset as given below

[1, 2, 4, 11, 15, 19, 26]

An array [19, 26, 1, 2, 4, 11, 15] has an offset of 2 as the smaller number starts from 2nd index and wrapping around to the first.

The assignment question is how to find an index of a number in array. For a sorted array, the solution would obviously be a binary search to find the index (with or without recursion).

How do you find the index of a number in an array with an offset? The offset is not known. I would like an outline for the solution and I will try to implement it in a language I am comfortable in.

Kartik
  • 2,541
  • 2
  • 37
  • 59
  • I 'm not sure what you are asking. For a trivial case with zero offset, the index of `x` is `x - 1` -- there is no need for binary search. For the general case where the array has an offset, the offset is obviously `1 - array[0] + N`. So again it's very easy to find the index of any number with a modulo operation. Am I missing something? – Jon Aug 18 '13 at 18:26
  • @Jon - The example array was a simplification. The numbers do not have to be an in ascending or descending order with a fixed numerical difference between them. They can be in any order. – Kartik Aug 18 '13 at 18:34
  • @Kartik: OK, makes sense now. – Jon Aug 18 '13 at 18:35
  • @PeterdeRivaz How would I find the find pivot element? I don't know what the offset is. – Kartik Aug 18 '13 at 18:40
  • Your numbers must be all different, otherwise the problem has no solution in less than `O(N)`. That was a spoiler. – n. m. could be an AI Aug 18 '13 at 19:11

1 Answers1

0

Find the largest element of the array with ternary search. So let's assume X is the index of the largest element of the array. So the offset will be X+1, if X < N-1, otherwise offset=0.

Then you can make two binary searches for eash element to find index of that number. First one will run in the range from 0 - (offset-1) and the second will be between offset - N. If you're allowed to use more space then you can also append the array to itself and then for each query make a single binary search from offset - (N+offset-1)

Fallen
  • 4,435
  • 2
  • 26
  • 46