recherche_dichotomique.js

// La recherche dichotomique en JS

// ENTREE -> Algo -> SORTIE

// ENTREE: dictionnaire + le mot à chercher
// SORTIE: -1 OU position

// cf. Code in Game / HackerRank

// dummyIndexOf 1s -> 200000 2s -> 400000

// simplonIndexOf


function dummyIndexOf(dictionnary, word) { // liste de mot quelconque
	var position = 0;
	while (position < dictionnary.length) {
		if (dictionnary[position] == word) {
			return position;
		}
		position++;
	}
	return -1;
}

function simplonIndexOf(dictionnary, word) { // dictionnaire doit être trié
	var begin = 0;
	var end = dictionnary.length - 1;

	// on boucle jusqu'à avoir trouvé le mot ou pas
	while (begin != end) {
		console.log("[" + begin + ":" + end + "]");
		
		// On trouve la position milieu du dictionnaire
		distance = end - begin;
		position = begin + (distance / 2);
		position = Math.floor(position);

		// On décide de quel coter chercher
		if (word == dictionnary[position]) {
			return position;
		} else if (word > dictionnary[position]) {
			begin = position;
		} else if (word < dictionnary[position]) {
			end = position;
		}
	}

	return -1;
}


/** TESTS **/

var verlan = ["geonpi", "keuf", "keum", "meuf", "teuf", "zikmu"];

console.log("# dummyIndexOf:");
console.log("keuf: " + dummyIndexOf(verlan, "keuf"));
console.log("geonpi: " + dummyIndexOf(verlan, "geonpi"));
console.log("danke: " + dummyIndexOf(verlan, "danke"));
console.log("keum: " + dummyIndexOf(verlan, "keum"));
console.log("teuf: " + dummyIndexOf(verlan, "teuf"));

console.log("# simplonIndexOf:");
console.log("keuf: " + simplonIndexOf(verlan, "keuf"));
console.log("geonpi: " + simplonIndexOf(verlan, "geonpi"));
console.log("danke: " + simplonIndexOf(verlan, "danke"));
console.log("keum: " + simplonIndexOf(verlan, "keum"));
console.log("teuf: " + simplonIndexOf(verlan, "teuf"));

/** ***** **/