[Résolu] Recherche binaire avec plusieurs valeurs de sortie

Question

heraclys

15 Jan 2021 à 10:00

Bonjour,

J'ai un fichier JSON avec une liste de films et leur date. J'aimerais effectuer une recherche binaire me permettant de retourner tous les films de l'année que j'ai indiqué. Je ne vois pas du tout comment faire pour retourner plusieurs valeurs avec ce type de tri (qui m'est imposé), quelqu'un pourrait m'aiguiller ?

Merci !

Ma fonction de base :

function searchBinaire(searchItem, tab, start, end) {
    let m = start + Math.ceil((end - start) / 2);

    var timeStamp = tab[m]['release_date'] // le TimeStamp à convertir

    date = new Date(timeStamp * 1000); // pour obtenir le timeStamp en millisecondes

    let year = date.getFullYear();

    tab[m].release_date = year;

    if (tab[m].release_date == searchItem) {
        return tab[m];
    }
    if (tab[m].release_date > searchItem) {
        return searchBinaire(searchItem, tab, start, m - 1);
    } else {
        return searchBinaire(searchItem, tab, m + 1, end);
    }
}

Modifié par heraclys (18 Jan 2021 - 19:28)

parsimonhi

Modérateur

15 Jan 2021 à 14:09

Bonjour,

Avec un peu de chance, et si j'ai bien compris la question, ceci devrait fonctionner. La fonction searchBinaire() renvoie non plus le premier item qui convient, mais un tableau contenant tous les items qui conviennent (c'est à dire dont la date de sortie vaut searchItem).

function getItemYear(tab, m)
{
    var timeStamp = tab[m]['release_date'] // le TimeStamp à convertir
    date = new Date(timeStamp * 1000); // pour obtenir le timeStamp en millisecondes
    let year = date.getFullYear();
    return year;
}
function searchAround(searchItem, tab, m)
{
	// on construit un tableau contenant tous les items de même année
	var k=1, km=tab.length, r=[];
	r.push(tab[m]);
	while(((m-k) >= 0) && (getItemYear(tab, m-k) == searchItem))
	{
		r.push(tab[m-k]);
		k++;
	}
	k=1;
	while(((m+k) < km) && (getItemYear(tab, m+k) == searchItem))
	{
		r.push(tab[m+k]);
		k++;
	}
	return r;
}
function searchBinaire(searchItem, tab, start, end) {
    if(start > end) return []; // cas où aucun item ne convient
    let m = start + Math.ceil((end - start) / 2);
    let release_date = getItemYear(tab, m);
    if (release_date == searchItem) {
        return searchAround(searchItem, tab, m); // on retourne tous les items de même année
    }
    if (release_date > searchItem) {
        return searchBinaire(searchItem, tab, start, m - 1);
    }
    return searchBinaire(searchItem, tab, m + 1, end);
}

Amicalement,
Modifié par parsimonhi (15 Jan 2021 - 14:12)

Sujet clos

JavaScript, DOM et API Web HTML5

[Résolu] Recherche binaire avec plusieurs valeurs de sortie