sorted and shifted array

Discussion in 'C++' started by Vols, Jun 1, 2008.

  1. Vols

    Vols Guest

    I found the following question, and couldn't get the best answer:

    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
    Vols, Jun 1, 2008
    #1
    1. Advertising

  2. Vols

    Eric Pruneau Guest

    "Vols" <> a écrit dans le message de news:
    ...
    >I found the following question, and couldn't get the best answer:
    >
    > 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
    Eric Pruneau, Jun 1, 2008
    #2
    1. Advertising

  3. Vols

    Guest

    On Jun 1, 11:03 am, Vols <> wrote:
    > I found the following question, and couldn't get the best answer:
    >
    > 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
    , Jun 2, 2008
    #3
  4. Vols

    Jim Langston Guest

    Vols wrote:
    > I found the following question, and couldn't get the best answer:
    >
    > 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
    Jim Langston, Jun 2, 2008
    #4
  5. Vols

    Sze Guest

    On 1 Jun., 05:03, Vols <> wrote:
    > I found the following question, and couldn't get the best answer:
    >
    > 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.
    Sze, Jun 2, 2008
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kalpesh Parikh

    C to Pro COBOL Problem - Bytes Shifted by 4

    Kalpesh Parikh, Feb 5, 2004, in forum: C Programming
    Replies:
    4
    Views:
    470
    CBFalconer
    Feb 5, 2004
  2. howa
    Replies:
    4
    Views:
    311
    mlimber
    Oct 26, 2006
  3. Replies:
    1
    Views:
    553
    Bergamot
    Mar 13, 2007
  4. Eric Lilja

    "Shifted" insert in std::string

    Eric Lilja, Jul 19, 2007, in forum: C++
    Replies:
    6
    Views:
    310
    James Kanze
    Jul 20, 2007
  5. banker123

    Sorted Hash and or Array

    banker123, Nov 3, 2006, in forum: Perl Misc
    Replies:
    4
    Views:
    98
    banker123
    Nov 5, 2006
Loading...

Share This Page