Buscar un elemento en una array ordenada y rotada con duplicados

Dada una array arr[] que está ordenada y rotada, la tarea es encontrar un elemento en la array rotada (con duplicados) en tiempo O (log n). 
Nota: Imprima el índice donde existe la clave. En caso de respuesta múltiple imprima cualquiera de ellas

Ejemplos: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the index of the
// key in arr[l..h] if the key is present
// otherwise return -1
int search(int arr[], int l, int h, int key)
{
    if (l > h)
        return -1;
 
    int mid = l + (h - l) / 2;
    if (arr[mid] == key)
        return mid;
 
    // The tricky case, just update left and right
    if ((arr[l] == arr[mid])
        && (arr[h] == arr[mid]))
    {
        ++l;
        --h;
        return search(arr, l, h, key);
    }
 
    // If arr[l...mid] is sorted
    if (arr[l] <= arr[mid]) {
 
        // As this subarray is sorted, we can quickly
        // check if key lies in any of the halves
        if (key >= arr[l] && key <= arr[mid])
            return search(arr, l, mid - 1, key);
 
        // If key does not lie in the first half
        // subarray then divide the other half
        // into two subarrays such that we can
        // quickly check if key lies in the other half
        return search(arr, mid + 1, h, key);
    }
 
    // If arr[l..mid] first subarray is not sorted
    // then arr[mid... h] must be sorted subarray
    if (key >= arr[mid] && key <= arr[h])
        return search(arr, mid + 1, h, key);
 
    return search(arr, l, mid - 1, key);
}
 
// Driver code
int main()
{
    int arr[] = { 3, 3, 1, 2, 3, 3 };
    int n = sizeof(arr) / sizeof(int);
    int key = 3;
 
    cout << search(arr, 0, n - 1, key);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to return the index of the
    // key in arr[l..h] if the key is present
    // otherwise return -1
    static int search(int arr[], int l, int h, int key)
    {
        if (l > h)
            return -1;
     
        int mid = l + (h - l) / 2;
        if (arr[mid] == key)
            return mid;
     
        // The tricky case, just update left and right
        if ((arr[l] == arr[mid])
            && (arr[h] == arr[mid]))
        {
            l++;
            h--;
              return search(arr,l,h,key);
        }
     
        // If arr[l...mid] is sorted
        else if (arr[l] <= arr[mid])
        {
     
            // As this subarray is sorted, we can quickly
            // check if key lies in any of the halves
            if (key >= arr[l] && key <= arr[mid])
                return search(arr, l, mid - 1, key);
     
            // If key does not lie in the first half
            // subarray then divide the other half
            // into two subarrays such that we can
            // quickly check if key lies in the other half
            else
              return search(arr, mid + 1, h, key);
        }
     
        // If arr[l..mid] first subarray is not sorted
        // then arr[mid... h] must be sorted subarray
           else  if (key >= arr[mid] && key <= arr[h])
            return search(arr, mid + 1, h, key);
     
        return search(arr, l, mid - 1, key);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] ={3, 3, 1, 2, 3, 3};
        int n = arr.length;
        int key = 3;
     
        System.out.println(search(arr, 0, n - 1, key));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the index of the
# key in arr[l..h] if the key is present
# otherwise return -1
def search(arr, l, h, key) :
 
    if (l > h) :
        return -1;
         
    mid = (l + h) // 2;
    if (arr[mid] == key) :
        return mid;
 
    # The tricky case, just update left and right
    if ((arr[l] == arr[mid]) and (arr[h] == arr[mid])) :
        l += 1;
        h -= 1;
        return search(arr, l, h, key)
    # If arr[l...mid] is sorted
    if (arr[l] <= arr[mid]) :
 
        # As this subarray is sorted, we can quickly
        # check if key lies in any of the halves
        if (key >= arr[l] and key <= arr[mid]) :
            return search(arr, l, mid - 1, key);
 
        # If key does not lie in the first half
        # subarray then divide the other half
        # into two subarrays such that we can
        # quickly check if key lies in the other half
        return search(arr, mid + 1, h, key);
 
    # If arr[l..mid] first subarray is not sorted
    # then arr[mid... h] must be sorted subarray
    if (key >= arr[mid] and key <= arr[h]) :
        return search(arr, mid + 1, h, key);
 
    return search(arr, l, mid - 1, key);
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 3, 1, 2, 3, 3 ];
    n = len(arr);
    key = 3;
 
    print(search(arr, 0, n - 1, key));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the index of the
    // key in arr[l..h] if the key is present
    // otherwise return -1
    static int search(int []arr, int l, int h, int key)
    {
        if (l > h)
            return -1;
     
        int mid = l + (h - l) / 2;
        if (arr[mid] == key)
            return mid;
     
        // The tricky case, just update left and right
        if ((arr[l] == arr[mid])
            && (arr[h] == arr[mid]))
        {
            ++l;
            --h;
            return search(arr, l, h, key)
        }
     
        // If arr[l...mid] is sorted
        if (arr[l] <= arr[mid])
        {
     
            // As this subarray is sorted, we can quickly
            // check if key lies in any of the halves
            if (key >= arr[l] && key <= arr[mid])
                return search(arr, l, mid - 1, key);
     
            // If key does not lie in the first half
            // subarray then divide the other half
            // into two subarrays such that we can
            // quickly check if key lies in the other half
            return search(arr, mid + 1, h, key);
        }
     
        // If arr[l..mid] first subarray is not sorted
        // then arr[mid... h] must be sorted subarray
        if (key >= arr[mid] && key <= arr[h])
            return search(arr, mid + 1, h, key);
     
        return search(arr, l, mid - 1, key);
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = { 3, 3, 1, 2, 3, 3 };
        int n = arr.Length;
        int key = 3;
     
        Console.WriteLine(search(arr, 0, n - 1, key));
    }
}
 
// This code is contributed by AnkitRai01

<script>
    // Javascript implementation of the approach
     
    // Function to return the index of the
    // key in arr[l..h] if the key is present
    // otherwise return -1
    function search(arr, l, h, key)
    {
        if (l > h)
            return -1;
      
        let mid = parseInt((l + h) / 2, 10);
        if (arr[mid] == key)
            return mid;
      
        // The tricky case, just update left and right
        if ((arr[l] == arr[mid])
            && (arr[h] == arr[mid]))
        {
            ++l;
            --h;
            return search(arr, l, h, key)
        }
      
        // If arr[l...mid] is sorted
        if (arr[l] <= arr[mid])
        {
      
            // As this subarray is sorted, we can quickly
            // check if key lies in any of the halves
            if (key >= arr[l] && key <= arr[mid])
                return search(arr, l, mid - 1, key);
      
            // If key does not lie in the first half
            // subarray then divide the other half
            // into two subarrays such that we can
            // quickly check if key lies in the other half
            return search(arr, mid + 1, h, key);
        }
      
        // If arr[l..mid] first subarray is not sorted
        // then arr[mid... h] must be sorted subarray
        if (key >= arr[mid] && key <= arr[h])
            return search(arr, mid + 1, h, key);
      
        return search(arr, l, mid - 1, key);
    }
     
    let arr = [ 3, 3, 1, 2, 3, 3 ];
    let n = arr.length;
    let key = 3;
 
    document.write(search(arr, 0, n - 1, key));
         
</script>