Differenza tra ricerca binaria di base per limite superiore e limite inferiore?

Question

Nell'articolo http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch, l'autore discute della ricerca binaria. Fa una distinzione tra trovare il valore più basso in cui qualcosa è vero, e il valore più alto in cui qualcosa è falso. L'array di essere cercato sembra qualcosa di simile:

false false false true true

Sono curioso di sapere perché questi due casi sono diversi. Perché non riesci a trovare il valore più basso che è vero, quindi sottrai uno per trovare il valore più alto che è falso?

Edit2: Ok, quindi capisco lower vs upper bound. Ora, sto cercando di capire, quando cerco il numero più piccolo maggiore o uguale alla query, perché non possiamo semplicemente cambiare lo if(mid>query) in if(mid>=query) e farlo fare più in basso che in alto.

Edit: Ecco ciò che l'articolo afferma:

"Ora abbiamo finalmente arriviamo al codice che implementa la ricerca binaria, come descritto in questo e nel precedente paragrafo:

binary_search(lo, hi, p): 
    while lo < hi: 
     mid = lo + (hi-lo)/2 
     if p(mid) == true: 
     hi = mid 
     else: 
     lo = mid+1 

    if p(lo) == false: 
     complain    // p(x) is false for all x in S! 

    return lo   // lo is the least x for which p(x) is true 

...

Se volessimo trovare gli ultimi x per i quali p (x) è falsa, dovremmo inventare (utilizzando una logica simile come sopra) qualcosa come:

binary_search(lo, hi, p): 
    while lo < hi: 
     mid = lo + (hi-lo+1)/2 // note: division truncates 
     if p(mid) == true: 
     hi = mid-1 
     else: 
     lo = mid 

    if p(lo) == true: 
     complain    // p(x) is true for all x in S! 

    return lo   // lo is the greatest x for which p(x) is false 

. "

Answer 1

Il limite inferiore e superiore di una ricerca binaria sono la posizione più bassa e più alta in cui è possibile inserire il valore senza interrompere l'ordine. (Nella libreria C++ principio tali limiti saranno rappresentati dalla iteratori fanno riferimento all'elemento prima che potrebbe essere inserito il valore, ma il concetto non viene sostanzialmente modificato.)

Prendere, per esempio, una serie ordinata

1 2 3 4 5 5 5 6 7 9 

in una ricerca binaria per 3, avremo

v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
    ^-- upper bound 

E in una ricerca binaria per 5:

 v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
      ^-- upper bound 

Il limite inferiore e superiore sono gli stessi se l'elemento non esiste nell'intervallo.In una ricerca binaria per 8:

    v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
       ^-- upper bound 

L'autore dell'articolo a cui si fa riferimento frasi tutto questo in termini equivalenti di "più piccolo" e "maggiore di" in modo che in una ricerca di 5,

 v-- lower bound 
t t t t f f f f f f  <-- smaller than? 
1 2 3 4 5 5 5 6 7 9 
f f f f f f f t t t  <-- greater than? 
      ^-- upper bound 

Gli iteratori C++, in tutti questi casi, si riferiscono all'elemento direttamente dietro il limite. Vale a dire:

• Nella ricerca 3, l'iteratore restituito da std::lower_bound sarebbe fare riferimento alla 3 e quello da std::upper_bound potrebbe fare riferimento a 4
• Nella ricerca 5, l'iteratore restituito da std::lower_bound sarebbe fare riferimento alla prima 5 e quella da std::upper_bound rimanda alla 6
• Nella ricerca di 8, entrambi avrebbero fare riferimento a 9

Questo perché la convenzione nella libreria standard C++ per gli inserimenti consiste nel passare un iteratore che fa riferimento all'elemento prima del quale il nuovo elemento deve essere inserito. Ad esempio, dopo

std::vector<int> vec { 1, 3, 4, 5, 5, 5, 6, 7, 9 }; 
vec.insert(vec.begin() + 1, 2); 

vec conterrebbe 1, 2, 3, 4, 5, 5, 5, 6, 7, 9. std::lower_bound e std::upper_bound seguire questa convenzione in modo che

vec.insert(std::lower_bound(vec.begin(), vec.end(), 5), 5); 
vec.insert(std::upper_bound(vec.begin(), vec.end(), 8), 8); 

lavoro come desiderato e lasciare vec ordinato.

Più in generale, questa è un'espressione del modo in cui gli intervalli sono specificati nella libreria standard C++. L'iteratore iniziale di un intervallo si riferisce al primo elemento dell'intervallo (se presente), mentre l'iteratore finale si riferisce all'elemento (se presente) direttamente dietro la fine dell'intervallo. Un altro modo per vederlo è che gli iteratori restituiti da std::lower_bound e coprono l'intervallo di elementi nell'intervallo cercato che sono equivalenti all'elemento cercato.

Questa gamma è vuoto se l'elemento non è nella gamma, in modo che lower_bound e upper_bound restituire la stessa iteratore, e altrimenti lower_bound restituisce un iteratore riferimento al primo elemento della gamma ricercate che è equivalente al valore di ricerca, mentre upper_bound restituisce un iteratore che fa riferimento all'elemento (se presente) direttamente dietro l'ultimo di tali elementi.

Answer 2

Se l'array sarà sempre

false … true … 

Poi l'indice prima di quello che si trova sarà sempre falso se non si trova affatto vero index 0. Un altro caso limite, come menzionato nel mio commento sopra, è se non trovi true. Quindi, il falso più alto sarà l'ultima parte dell'array.

Answer 3

I due algoritmi, ovviamente, differiscono nella condizione di ciò che dovrebbe accadere se non ci sono c'è true o nessun valore false come è in realtà abbastanza evidente dal frammento di codice: se si trova il valore più basso in cui il valore è true e sottrarre 1 da questa posizione per trovare il valore più alto che produce false viene generato un risultato errato in quanto non esiste tale oggetto. Poiché gli algoritmi si limitano a colpire diversi elementi che si occupano di localizzare direttamente l'elemento appropriato piuttosto che avere un caso speciale evita anche di dover gestire un caso speciale, riducendo la quantità di codice. Poiché il codice di caso speciale tende ad essere eseguito solo una volta per ogni richiamo dell'algoritmo, è probabile che funzioni leggermente peggio che evitare il caso speciale. Questo è qualcosa che potrebbe valere la pena di misurare.

Si noti che l'esempio di codice non è C++ nonostante la domanda venga codificata in C++. Di conseguenza non è un C++ idiomatico. L'approccio tipico in C++ per implementare qualcosa come lower_bound() o upper_bound() consiste nell'utilizzare iteratori appropriati. Questi algoritmi non "protestano" se non esiste un elemento adatto in quanto producono solo un iteratore nella posizione appropriata, cioè un iteratore all'inizio per std::lower_bound() e un iteratore passato-fine per std::upper_bound().