Rencontre #37: Recherche binaire

Problèmes

Le nombre à côté de chaque problème indique son niveau de difficulté selon Kattis.

1. “Synchronizing Lists” 1.6 — Reorganisez la deuxième liste pour qu’elle corresponde à l’ordre de la première liste en respectant les correspondances des identifiants après tri.

   • “Binary Search” Easy — Problème plus facile sur Leetcode.

2. “Out of Sorts” 2.3 — Si on exécute une recherche binaire dans un tableau non-trié, combien de valeurs sont impossibles à retrouver?

   • “Search a 2D Matrix” Medium — Problème différent, mais utilisant la recherche binaire.

3. “Room Painting” 2.5 — On souhaite acheter de la peinture de plusieurs couleurs à une compagnie qui la vend dans des contenants de taille fixe. Étant données les quantités de peinture souhaitées, combien de peinture sera gâchée au minimum?

   • “Koko Eating Bananas” Medium — Problème intéressant démontrant l’utilité de la recherche binaire sous un autre angle.

4. “Firefly” 2.9 — Une luciole doit traverser en ligne droite horizontale une séquence d’obstacles verticaux. À quelle hauteur doit-on placer la luciole pour qu’elle croise le moins d’obstacles possible?

   • “Find Minimum in Rotated Sorted Array” Medium — Problème de binary search sur Leetcode.