Scrittura di un algoritmo di ricerca binaria per trovare la posizione del valore

Question

Scrittura di un algoritmo di ricerca binaria per trovare la posizione del valore

#1 da (0 voti)

-5

In realtà sto solo cercando lo pseudo codice qui.

Sto provando a scrivere una ricerca binaria che trova la posizione di un valore in una serie di valori (o la posizione in cui un valore dovrebbe essere in una serie quando il valore non esiste).

Mi viene imposto un arrotondamento quando la quantità di valori di una serie è dispari. Non sono sicuro se dovrei arrotondare per eccesso o per difetto o in entrambi i casi o in un modo in alcuni casi o in un altro.

Dati di esempio: 1,2,3,5,6,7,8

Devi restituire correttamente la posizione per "4", "7", "9".

algorithms

posta David 06.06.2017 - 12:25

fonte

1 risposta

Leggi altre domande sui tag algorithms

Utilizzare Angular2 per sito Web e API per l'applicazione mobile con un progetto di singola API Web Come faccio a ottenere python per riconoscere il mio file DLL come import (in grado)

score 0 · Answer 1

Quando partizionate il vostro insieme di valori, non importa quale delle due metà l'elemento dispari finisce. Il peggio che potrebbe accadere è che l'elemento che state cercando si trova nella partizione più grande, che significa che avrai bisogno di un confronto più del caso migliore (dove l'elemento è coerente nella partizione più piccola).

Puoi testarlo facilmente dividendo ripetutamente un set di dati di esempio e vedendo quale è l'effetto della scelta dell'arrotondamento.

Ad esempio, con arrotondamenti costanti, otterresti queste partizioni per il tuo set di dati a 7 elementi

|1 2 3 5 6 7 8|
|1 2 3|5 6 7 8|
|1|2 3|5 6|7 8| <- first element in a partition by its own
|1|2|3|5|6|7|8| <- all elements in a partition by themselves