Minimo in sequenza ciclicamente ordinata

[^Coman]

Intanto per chi non lo sapesse una sequenza ordinata di n elementi distiniti a1,a2,...,an si dice ciclicamente ordinata quando il piu' piccolo elemento e' ai , per un qualche indice i non noto, e la sequenza ai,ai+1,...,an,a1,...,ai-1 e' ordinata in modo crescente.

Praticamente il problema e' di fare l'algoritmo che calcola il minimo di una sequenza ciclicamente ordinata di n elementi in tempo O(logn).

Pensavo di basarmi sull'algoritmo della ricerca binaria, visto che effettuando una ricerca sequenziale sicuramente il tempo e' maggiore di O(logn), pero' ci deve essere qualcosa che mi sfugge qualcuno sa darmi qualche indicazione?

Grazie

[cionci]

Fammi capire...tu hai giò una sequenza ordinata ciclicamente e devi trovare il minimo ai ?

Se è così puoi proprio fare con una ricerca binaria:

int ricercabinaria(int *v, int i, int inizio, int fine)

inizio e fine sono i limiti di ricerca e ti serviranno per calcolarti gli spostamenti (si inizializzano a 0 e N-1 nella prima chiamata)...

La condizione di arresto è questa (attento agli estremi):

if(a[i+1] >= a[i] && a[i-1] > a[i])

attento che non funziona nel caso particolare in cui tutti i numeri siano uguali

Altrimenti vai a valutare due indici per spostarti nella direzione giusta di ricerca:

if(a[inizio + (i - inizio) / 2] >= a[i])

Chiami ricorsivamente la ricerca sull'elemento inizio + (i - inizio) / 2 (attento ai parametri da passare)

ifif(a[i + (fine - i) / 2] >= a[i])

Chiami ricorsivamente la ricerca sull'elemento i + (fine - i) / 2 (attento anche qui ai parametri da passare)

[^Coman]

Fammi capire...tu hai giò una sequenza ordinata ciclicamente e devi trovare il minimo ai ?



Si esattamente.



Se è così puoi proprio fare con una ricerca binaria:

int ricercabinaria(int *v, int i, int inizio, int fine)

inizio e fine sono i limiti di ricerca e ti serviranno per calcolarti gli spostamenti (si inizializzano a 0 e N-1 nella prima chiamata)...

La condizione di arresto è questa (attento agli estremi):

if(a[i+1] >= a[i] && a[i-1] > a[i])

attento che non funziona nel caso particolare in cui tutti i numeri siano uguali



E infatti fino qui c'ero arrivato. L'unica cosa la i che gli passi sarebbe la parte intera superiore di n-1/2?



Altrimenti vai a valutare due indici per spostarti nella direzione giusta di ricerca:

if(a[inizio + (i - inizio) / 2] >= a[i])

Chiami ricorsivamente la ricerca sull'elemento inizio + (i - inizio) / 2 (attento ai parametri da passare)

ifif(a[i + (fine - i) / 2] >= a[i])

Chiami ricorsivamente la ricerca sull'elemento i + (fine - i) / 2 (attento anche qui ai parametri da passare)

Queste invece son le condizioni che non riuscivo a trovare...cosa intendi di preciso con "chiami ricorsivamente la ricerca sull'elemento inizio + (i - inizio) / 2 (attento ai parametri da passare)" cioe' io in quel punto dovrei ridurre i limiti di ricerca. E pensavo sposatandomi verso sinistra nella prima condizione e verso destra nella seconda. Pero' provando un attimo a mente sinceramente non mi funziona :fagiano:

Grazie intanto dell'aiuto.

[cionci]

La seconda condizione l'ho sbagliata ;) A questo punto metto anche la chaimata:

if(a[i + (fine - i) / 2] > a[i])
return ricercabinaria(a, i + (fine - i) / 2, i, fine);

Per l'altro if la chiamata diventa:

ricercabinaria(a, inizio + (i - inizio) / 2, inizio, i);