electroRF
Member
Hi,
I'm facing this problem which I don't manage to solve.
You got a sorted array of size N, that was shifted by unknown shifting.
i.e. instead of {1,2,3,4,5,6,7,8} it became: {6,7,8,1,2,3,4,5}.
You're given a number and need to tell if it's in the array, and in which index.
You need to do this in log(N).
How do you do that?
I thought of making a binary search, first for finding the original start of the array.
Then split it to 2 arrays, and make another binary search.
This will result in log(N).
However,
How can you find the original start of the array in this case: {2,1,2,2,2} or {2,2,2,1,2}, in log(N)?
Thank you!
I'm facing this problem which I don't manage to solve.
You got a sorted array of size N, that was shifted by unknown shifting.
i.e. instead of {1,2,3,4,5,6,7,8} it became: {6,7,8,1,2,3,4,5}.
You're given a number and need to tell if it's in the array, and in which index.
You need to do this in log(N).
How do you do that?
I thought of making a binary search, first for finding the original start of the array.
Then split it to 2 arrays, and make another binary search.
This will result in log(N).
However,
How can you find the original start of the array in this case: {2,1,2,2,2} or {2,2,2,1,2}, in log(N)?
Thank you!