Trova l'elemento minimo in un array, che ha un modello

Question

Un array viene fornito in modo che il valore del suo elemento aumenti da 0th index ad alcuni (k -1) indice. A k il valore è minimo, e poi inizia ad aumentare nuovamente attraverso l'elemento n. Trova l'elemento minimo.

In sostanza, la sua lista ordinata si aggiungeva a un'altra; esempio: (1, 2, 3, 4, , 1, 2, 3).

Ho provato tutti i tipi di algoritmi come il cumulare di min-heap, la selezione rapida o il semplice attraversamento. Ma non posso farlo sotto O (n). Ma c'è un modello in questo array, qualcosa che suggerisce che un tipo di ricerca binaria dovrebbe essere possibile, e la complessità dovrebbe essere qualcosa come O (log n), ma non riesco a trovare nulla. Pensieri ??

Grazie

Answer 1

No Il calo può essere ovunque, non esiste una struttura a questo.

consideri gli estremi

1234567890 
9
1234056789 
1357024689 

Si riduce di trovare l'elemento minimo.

Answer 2

Effettuare una ricerca binaria in larghezza per un intervallo decrescente, con una sovrapposizione di un elemento alle divisioni binarie. In altre parole, se si ha, ad esempio, 17 elementi, confrontare gli elementi

0,8 
8,16 
0,4 
4,8 
8,12 
12,16 
0,2 
2,4 

ecc, alla ricerca di un caso in cui l'elemento di sinistra è maggiore di quello destro.

Una volta trovato tale intervallo, recurse, facendo la stessa ricerca binaria all'interno di tale intervallo. Ripeti fino a quando non trovi la coppia adiacente decrescente.

La complessità media non è inferiore a O (log n), con il caso peggiore di O (n). Qualcuno può ottenere una valutazione della complessità media più ristretta? Sembra approssimativamente "a metà strada tra" O (log n) e O (n), ma non vedo come valutarlo. Dipende anche da eventuali vincoli aggiuntivi sugli intervalli di valori e le dimensioni dell'incremento da un membro a quello successivo.

Se l'incremento tra gli elementi è sempre 1, esiste una soluzione O (log n).

Answer 3

Non può essere eseguito in meno di O (n).

Il caso peggiore di questo tipo saranno sempre tenerci preoccupante -

Una lista crescente a1, a2, a3 .... ak, ak + 1 ... un

con un solo scarto ak < ak-1 ad es 1,2,3,4,5,6,4,7,8,9,10

E tutti gli altri numeri tengono assolutamente a zero informazioni su valore di 'k' o 'ak'

Answer 4

La soluzione più semplice è solo guardare avanti alla lista fino a quando il valore successivo è inferiore a quello corrente, o all'indietro per trovare un valore maggiore di quello corrente. Questo è O (n).

Entrambi contemporaneamente sarebbero ancora O (n), ma il tempo di esecuzione sarebbe probabilmente più veloce (a seconda di complicati fattori di processore/cache).

Non penso che si possa ottenere molto più velocemente algoritmicamente di O (n) poiché molti degli algoritmi di ricerca divide e conquista si basano sull'avere un set di dati ordinato.