[JAVA] Ricerca indice in array ciclico

[Poker1]

Ciao a tutti!!!!
Io ho un array ciclicamente ordinato tipo questo:

12 14 20 1 3 7 10 11

Dovrei scrivere una funzione ( con il metodo divide et-impera ) che mi trova l'indice del ciclo, in questo caso sarebbe 3.

Io ho diviso l'array a meta' con centro = (sx + dx)/2 solo che in questo modo a meno che non prendo l'elemento esatto che ha la caratteristica di avere l'elemento alla sua destra e l'elemento alla sua sinistra entrambi maggiori di lui, non so come fare. Cioe' essendo ordinati tutti gli altri elementi non riesco a trovare una legge che mi permetta di andare a cercare l'indice o a destra o a sinistra ( dato che devo farlo con complessita' log n )

Grazie a tutti per i suggerimenti :P

[Andrea1979]

allora, potresti fare:

- scegli l'elemento centrale della tua partizione corrente

se arr[mid-1] > arr[mid] hai finito, altrimenti

- se arr[last] < arr[mid] la tua nuova partizione sarà first = mid+1 e last = last
- altrimenti first = first, last = mid -1

Domanda: funziona?

[Poker1]

praticamente dici di fare

- se non trovo l'elemento nella posizione centrale dell'array,

- se arr[dx] < arr[centro] cerco nella meta' destra

- altrimenti cerco nella meta' di sinistra?

[Poker1]

public static int cercaIndice( int[] a, int sx, int dx )
	{
		int centro = (sx+dx) / 2;
		
		System.out.println( "Centro vale: " + centro );
		
		if( a[(centro+1) % a.length]  > a[centro] && a[(centro-1)%a.length]  > a[centro] )
		{
			System.out.println("Trovato l'indice in posizione " + centro);
			return centro;
		}		
		else
			if( a[centro] > a[dx] )
				cercaIndice( a, centro+1, dx);
			else
				cercaIndice( a, sx, centro-1);
		
		return centro;
	}

Ok funziona, a parte quell'ultimo return centro che l'ho messo per far star zitto il complilatore, altrimenti mi dice che la funzione deve ritornare u n valore intero ( se provi ad eseguirla devi far fede solo alla stampa dentro l'if ).

La cosa che non capisco ancora e'..che relazione c'e' quindi tra l'elemento che esamino e sx e dx ?

[Andrea1979]

  public int rot(int first, int last) {
    int mid = (first + last)/2;
    if (mid==0 || a[mid-1] > a[mid]) {
      return mid;
    }
    else {
      if (a[last] < a[mid]) {
        return rot(mid+1, last);
      }
      else {
        return rot(first, mid-1);
      }
    }
  }

Per forza di cose (visto che l'array è ordinato in ordine crescente) se l'elemento a sx di quello considerato è maggiore di quello considerato allora tale elemento a sinistra è pure il più grande nell'array e quindi l'elemento considerato è il primo (il più piccolo) ed occupa la posizione di ordine "n° rotazioni". Non te ne fai niente dell'elemento a dx (salvo che l'array non sia ordinato in senso decrescente).