Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   sorted and shifted array (http://www.velocityreviews.com/forums/t617869-sorted-and-shifted-array.html)

 Vols 06-01-2008 03:03 AM

sorted and shifted array

if you have a sorted and shifted array such like {5,6,7,1,2,3,4}, how
to find one element "2"?

Thanks.
Vol

 Eric Pruneau 06-01-2008 02:00 PM

Re: sorted and shifted array

"Vols" <volunteers@gmail.com> a écrit dans le message de news:
>
> if you have a sorted and shifted array such like {5,6,7,1,2,3,4}, how
> to find one element "2"?
>
> Thanks.
> Vol

Check out algorithms like

std::find, std::find_if

int arr[5] = {1,2,3,4,5}
int* it = std::find(arr, arr+5, 2); // it now point to arr[1]

and you can use std::distance to obtain the position of the element

 kongweize@gmail.com 06-02-2008 05:55 AM

Re: sorted and shifted array

On Jun 1, 11:03*am, Vols <volunte...@gmail.com> wrote:
>
> if you have a sorted and shifted array *such like {5,6,7,1,2,3,4}, how
> to find one element "2"?
>
> Thanks.
> Vol

the sorted and shifted array contains 2 sorted subsequence
first, find the 2 subsequence
then check which subsequence is the element in, and do binary search

 Jim Langston 06-02-2008 07:49 AM

Re: sorted and shifted array

Vols wrote:
>
> if you have a sorted and shifted array such like {5,6,7,1,2,3,4}, how
> to find one element "2"?

Your requirements are not clear. Do you need to find the element that
contains the value 2, or the element that was orignally the 2nd element
before the shift?

--
Jim Langston
tazmaster@rocketmail.com

 Sze 06-02-2008 03:40 PM

Re: sorted and shifted array

On 1 Jun., 05:03, Vols <volunte...@gmail.com> wrote:
>
> if you have a sorted and shifted array such like {5,6,7,1,2,3,4}, how
> to find one element "2"?

If you meant that every unshifted sequence, you want to search through
has
in general the form {1,2,3,4,...,n}|n = amount of elements

You could easily calculate about how many elements it is shifted,
through:
shiftingRange = n - (firstValue - 1)
this algorithm would return 7 if firstValue is 1, which is the same
sequence
because it`s a full shift, but 0 would be nicer, to get this you could
do this:
shiftingRange = (n - (firstValue - 1))%n
So you would get the index of the value you are searching for with
find(x) = (shiftingRange + x - 1) % 7 // -1 to make it a c++ array
index, which starts by zero

find(2) = ((7 - (5 - 1))%7 + 2 - 1) % 7 = 4 // with your sequence as
example
find(5) = (3 + 5 - 1) % 7 = 0

My answer is just a guess of what you could have meant,
you should represent what do you want to achieve.

 All times are GMT. The time now is 11:18 PM.