Visualizzazione dei risultati da 1 a 2 su 2
  1. #1
    Utente di HTML.it
    Registrato dal
    Oct 2003
    Messaggi
    1,258

    ricerca binaria, con numeri ripetuti..è possibile?

    Sebbene mi è stato detto che è possibile, io ho i miei dubbi.
    Trattasi, di fare una ricerca binaria in un array di elementi ordinati con possibili doppi.

    Il problema però secondo me sorge in questo caso:

    1,2,3,3,5,7,9
    cerchiamo 3, il programma una volta fatta la metà dell'array(fra 0 e 6, elemento 3) non può sapere da che parte continuare a cercare, se andare a sinistra o a destra, dico bene? :bubu:

    quindi se va dalla parte sbagliata perde uno o piu elementi che doveva contabilizzare.

    dovrei usare infatti questa ricerca per restituire un array con l'elenco delle posizioni dell'elemento cercato...
    Ma per il motivo suddetto bisognerebbe modificare troppo l'algoritmo, per fargli prendere la strada giusta nella ricerca..

    Saluti da Luca

  2. #2
    Utente di HTML.it L'avatar di anx721
    Registrato dal
    Apr 2003
    Messaggi
    2,352
    Se trovi un elemento nell'array io continuerei a leggere linearmente l'array sia a destra che a sinistra finche trovo elementi uguali a quello che cerco. Ovviamente, il numero di passi compiuto non è piu logaritmico in generale,

    ciao.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.