[Algoritmi] Prestazioni caso medio: ricerca binaria di un x>k

[Patras1]

Salve! Mi è venuto in mente questo caso: viene dato un $k \in [a, b]$. Avendo un array contenente $n$ valori dell'intervallo $[a,b]$ trovare le prestazioni nel caso medio della ricerca binaria di un qualsiasi $x>k$ tale che $x$ appartiene all'array.

Caso migliore ovviamente è $O(1)$. Caso peggiore $O(\log n)$
E caso medio?
Credo che mediamente rimanga $O(\log n)$ però non sono sicuro e non so dimostrarlo. Forse dipende anche dall'intervallo $[a, b]$ ? Ho studiato gli alberi di decisione ma non riesco a capire come funziona in questo caso

[apatriarca]

Alcuni chiarimenti. I valori sono distinti e ordinati? Dalla tua descrizione sembra tu stia parlando di un valore \(x\) qualsiasi nell'array che sia più grande di \(k\). Immagino che la richiesta sia di trovare il valore più piccolo con questa proprietà. È corretto? Inoltre hai scritto \(x > k\) e quindi in particolare \(x \neq k.\) Normalmente si cerca \(x \geq k\). È un errore nello scrivere il post o è effettivamente questa la condizione che stai cercando?

Credo che la risposta sia effettivamente \(O(\log\,n)\) comunque. Sulla dimostrazione devo però pensarci.

[Patras1]

Scusa ma scrivevo di fretta... si l'array è ordinato avente elementi distinti. Non ci avevo pensato perché l'ho inventato io ma facciamo allora $x \geq k $

[apatriarca]

A meno di scegliere un valore che sia contenuto nell'array (la cui probabilità scende con l'aumentare del rapporto tra numero di elementi e grandezza dell'intervallo), il tuo algoritmo richiede di arrivare all'ultimo livello della ricorsione per cui direi che è sufficiente per dire che il caso peggiore è anche quello medio.