Per trovare l'elemento minimo in un array che è ordinata e ruotato

Question

Recentemente ho affrontato un problema di programmazione che è la seguente:

un array ordinato è dato e l'array è ruotato ad un certo punto sconosciuto, devo trovare l'elemento minimo in esso. La matrice può contenere anche duplicati.

Per esempio:

Input: {5, 6, 1, 2, 3, 4} 

Output: 1 

Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} 

Output: 0 

I seguita soluzione semplice è quella di attraversare trogolo la gamma completa e trova minimo. Questa soluzione richiede tempo O (n). Comprendo il fatto che l'elemento minimo è quello il cui elemento precedente è maggiore di esso. Se non è presente un tale elemento, allora non c'è rotazione e il primo elemento sarebbe il minimo.

Ma mi è stata chiesta una soluzione O (Logn). C'è un modo per risolverlo in tempo O (Logn)?

Answer 1

Fuori della parte superiore della mia testa:

• Nota la prima voce
• Eseguire una ricerca binaria; in ogni fase scegli la metà destra se l'elemento pivot è maggiore o uguale al primo elemento memorizzato e la metà sinistra se l'elemento pivot è minore.

Per esempio, dato {4,5,6,7,1,2,3}:

• Pivot a 7>4, ridurre alla metà destra {1,2,3}
• Pivot a 2 < 4, ridurre a metà sinistra 1.
• Considerando un solo elemento, la risposta è 1.

Answer 2

vedere questo: Poiché è ordinato array. Ho bisogno di applicare la ricerca binaria per trovare pivot ..

L'elemento più basso sarà dove la matrice è stata ruotata.

chiamata questa findpivot(arr,0,n-1);

int findPivot(int arr[], int low, int high) 
{ 
    // base cases 
    if (high < low) return -1; 
    if (high == low) return low; 

    int mid = (low + high)/2; /*low + (high - low)/2;*/ 
    if (mid < high && arr[mid] > arr[mid + 1]) 
    return mid; 
    if (mid > low && arr[mid] < arr[mid - 1]) 
    return (mid-1); 
    if (arr[low] >= arr[mid]) 
    return findPivot(arr, low, mid-1); 
    else 
    return findPivot(arr, mid + 1, high); 
}