How to get the pivot point in a sorted rotated array with duplicate elements iteratively?

Question

Finding the pivot point in a rotated sorted array with duplicates using loop. Though I found a solution in suggestion but that was using recursion. I need a solution using recursion. I am stuck with this problem from the last 12hours. Any help would be highly appreciated.

Until now I have tried finding the cell which has both the elements around it greater than the element itself. But it does not seem to be working. Can anyone tell me where am I going wrong.

int findPivot(vector<int>& nums)
{
    int lo=0,hi=nums.size()-1,mid,n=nums.size();
    while(lo<=hi)
    {
        mid = (lo+hi)>>1;
        if(nums[(mid+1)%n] >= nums[mid] && nums[(mid-1+n)%n]>nums[mid])
            return mid;
        if(nums[mid]>nums[hi])
            lo = mid+1;
        else
            hi = mid-1;
    }
    return 0;
}

But it does not seem to be working for cases like this [3,1] where I am getting 0, the expected output is 1 and [1,1,3,1] 3 where I am getting 0.

Off-topic: You don't modify the vector, so the reference should be const. — Aconcagua, Mar 23 '19 at 15:15
Correct const-ness won't solve anything of the true problem you are suffering, so... — Aconcagua, Mar 23 '19 at 15:49

Aconcagua · Answer 1 · 2019-03-23T17:22:43.767

Problem is here:

if(nums[mid] > nums[hi])

You cannot use this condition safely, and modifying it to using >= or in combination with nums[lo], to < or <= won't help either; consider the following two sequences:

{ 1, 1, 1, 2, 1 }
{ 1, 2, 1, 1, 1 }
  0     2     4
 lo    mid    hi

With any combination of lo or hi with any of above comparators, one of the two sequences will be evaluated the wrong way because of selecting the bad half! You ran into exactly such situation with your sequence { 1, 1, 3, 1 }.

So if you end up in such situation (nums[x] being equal for all of lo, hi and mid), you'd have to check both halfs! I suppose two recursive calls are easiest to implement. Be aware that you won't need to recurse if any of the values at the three indices differs; if you need to recurse, only for one of the two sub-results the real successor will be smaller, so this one will be the final result.

You could detect e. g. as follows:

if(nums[mid] > nums[hi] || nums[mid > nums[lo])
{
    hi = mid - 1;
}
else if(nums[mid] < nums[lo] || nums[mid] < nums[high]
{
    lo = mid + 1;
}
else
{
    int idxLo = findPivotRecursively(nums, lo, mid - 1);
    int idxHi = findPivotRecursively(nums, mid + 1, high);
    return nums[idxHi] > nums[(idxHi + 1) % n] ? idxHi : idxLo;
}

Provided you turned the function into a recursive one with signature

int findPivotRecursively(std::vector const& nums, int high, int low);

As the array is sorted, this last condition can only be true for either of idxLo or idxHigh; the test I chose will result in selecting first element of vector, if all elements are equal (nums[idxLo] > nums[(idxLo + 1] ? /*...*/; would select the last one).

A helper function would provide the public interface:

int findPivot(std::vector const& nums)
{
    return findPivotRecursively(nums, 0, nums.size() - 1);
}

With help of a lambda, you could hide away the working function entirely. Unfortunately, recursive lambdas are not supported directly, so you'd rely on a little trick as shown in this answer:

int findPivot(std::vector const& nums)
{
    size_t n = nums.size();
    auto findPivotRecursively = [&nums, &n] (int hi, int lo, auto& fpr) -> int
    {
        // ...
        else
        {
            int idxLo = fpr(hi, lo, fpr);
            // ...
        }
        // ...
    };
    return findPivotRecursively(0, nums.size() - 1, findPivotRecursively);
}

Please can you explain what exactly I need to add or change? — Kitpul Bhatt, Mar 23 '19 at 15:28
Every recursive algorithm can be turned into an iterative one. Problem about is that you need to store borders of lower and upper half somewhere, if you need to recurse. Depending on the algorithm, that can get a bit tricky; for comparison, [here](https://www.techiedelight.com/iterative-implementation-of-quicksort/) an iterative variant of quicksort; you could do something similar; your variant would be a bit more complicated, though, as you need to do further stuff after having sorted two halfs... — Aconcagua, Mar 23 '19 at 16:28

How to get the pivot point in a sorted rotated array with duplicate elements iteratively?

1 Answers1