CODEWITHSUNDEEP
c++algorithmsearchdata-structuresbinary-search
user4627889
user4627889

Reputation:

k-rotated-shifted array and finding x?

We say a k-rotated-shifted array, to an array such that with k rotate can be sorted. Example is : A=[10, 15, 20, 1, 7], with k=2. I propose an algorithm for finding a key like x in this k-rotated-shifted array.

anyone could help me to verify it?

enter image description here

Edit 1: my new code is:

 int S(int l, int r, int x)
{ int f=A[l], m=A[(l+r)/2], la=A[l];
if (x==f or x==m or x==la)
     return 1;
else {if ((x< f and x>m) || (x>f and x>m) || (x<f and x<m))
   return S((l+r)/2, r, x);
   else
    return S(l,(l+r)/2, x);
}
}

Upvotes: 1

Views: 139

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65508

Breaks finding 1 in 3,4,5,1,2. Breaks finding a key that is not present, because the base case triggers only when the key is found, causing an infinite loop.

To fix, use the condition

first < middle < x or middle < x < first or x < first < middle.

Also note that comparing with last is superfluous if we take the ceiling of (i + j) / 2.

Upvotes: 2

Related Questions