Ricerca binaria e i predicati

Raga secondo voi qual’è il miglior modo per fare una ricerca binaria all’interno di un intervallo (non vettore) per trovare il più alto/basso valore che soddisfa un predicato?
per esempio nel caso che dovessimo trovare il più alto valore nell’intervallo [0;100] che soddisfa p(x) = x<=60
PS: il predicato dell’esempio è inventato e certamente noi sappiamo che il valore è 60.

La richiesta dell’algoritmo è nata quando stavo facendo il problema lungomare

bool check(int N, long long int L, long long int D[], long long int P[], long long int S) { //... }
long long int testPercorso(int N, long long int L, long long int D[], long long int P[], long long int min, long long int max) { long long int mid; long long int last; while (min != max) { mid = (max+min)/2; //cout << "Try [" << min << ";" << max << "] " << mid; bool res = check(N,L,D,P,mid); if (res) { //cout << "...TRUE\n"; max = mid+1; } else { //cout << "...FALSE\n"; min = mid; } if (last == mid) return mid; last = mid; } return L; }

In che senso “qual’è il modo migliore”?
Comunque, ti consiglio quando cambi i valori di max e min tieni conto del fatto che mid è già stato analizzato… quindi se stai cercando il primo numero inferiore a un certo valore e ottieni res=true quando che controlli che mid soddisfi le condizioni, avrai min=mid+1; o viceversa se false max=mid-1…
Quando poi max e min si incrociano (non mi ricordo se debbano essere uguali oppure max<min) interrompi il ciclo…
O almeno, io ho sempre fatto così
Ovviamente non è detto che questo sia il modo migliore per applicarla al tuo problema specifico

Io ho usato questo codice in filiali bilanciate , quello che si doveva trovare era la distanza massima alla quale poter posizionare le filiali, ogni volta verifico se sia il valore corrente che il successivo funzionino, nel caso in cui entrambi sono veri, allora sposto l’inizio, nel caso in cui entrambi siano falsi allora sposto la fine, se il primo è vero e il secondo è falso allora avrò ottenuto il risultato che cerco.

Con questo codice inizio e fine possono avere qualsiasi valore quindi funzionano anche in un intervallo del vettore.

while(!finito && inizio<=fine)
	{
		centro=(fine-inizio)/2;
		centro+=inizio;
		bool a=filiale(centro), b=filiale(centro+1);
		if(a && b)
		{
			inizio=centro+1;
		}
		else if(!a && !b)
		{
			fine=centro-1;
		}
		else if(a && !b)
		{
            writeInt(centro);
			finito=true;
		}
	}
1 Mi Piace