Matières
Carrière
Maths
Physique/Chimie
Français
Histoire
SVT
Vision et image
L'énergie
Les transformations chimiques
Les états de la matière
Constitution et transformations de la matière
Ondes et signaux
Lumière, images et couleurs
Constitution et transformation de la matière
Mouvements et interactions
Structure de la matière
L'organisation de la matière dans l'univers
Les circuits électriques
Énergie : conversions et transferts
Propriétés physico-chimiques
Les signaux
Affiche tous les sujets
Le nouveau monde
Nouveaux enjeux et acteurs après la guerre froide
Les guerres mondiales
Le monde de l'antiquité
La méditerranée de l'antiquité au moyen-age
Le xviiième siècle
Le xixème siècle
La crise et la montée des régimes totalitaires
Le monde depuis 1945
Une nouvelle guerre mondiale
La guerre froide
Les religions du vième au xvème siècle
La 3ème république
Révolution et restauration
La france et la république
Affiche tous les sujets
Le monde microbien et la santé
Le stress
Unité et diversité des êtres vivants
Corps humain et santé
La planète terre, l'environnement et l'action humaine
La géologie
Reproduction et comportements sexuels responsables
La cellule unité du vivant
Transmission, variation et expression du patrimoine génétique
Procréation et sexualité humaine
La génétique
Le mouvement
Diversité et stabilité génétique des êtres vivants
Nutrition et organisation des animaux
Affiche tous les sujets
11
0
Chanel Lemaine
01/09/2025
NSI
Recherche dichotomique dans un tableau trié
422
•
1 sept. 2025
•
Chanel Lemaine
@chanizzle
La recherche dichotomiqueest un algorithme efficace pour trouver un... Affiche plus
La terminaison de l'algorithme de recherche dichotomique est cruciale pour garantir qu'il s'arrêtera toujours, quelle que soit l'entrée. Pour prouver la terminaison, on utilise le concept de variant de boucle.
Vocabulaire: Un variant de boucle est une valeur entière positive ou nulle qui décroît strictement à chaque itération de la boucle.
Dans le cas de la recherche dichotomique, le variant de boucle est la différence entre les indices droite et gauche. Cette valeur décroît strictement à chaque itération, assurant ainsi la terminaison de l'algorithme.
La correction de l'algorithme est démontrée en utilisant la technique de l'invariant de boucle. Un invariant de boucle est une proposition qui reste vraie à chaque itération.
Définition: Un invariant de boucle pour la recherche dichotomique est : "Si la valeur recherchée est dans le tableau, son indice est compris entre gauche et droite."
La démonstration de la correction montre que cet invariant reste vrai pour chacun des trois cas possibles à chaque itération : la valeur est trouvée, elle est dans la moitié gauche, ou elle est dans la moitié droite.
Highlight: La preuve de terminaison et de correction garantit que l'algorithme de recherche dichotomique fonctionne correctement et s'arrête toujours, ce qui est essentiel pour son utilisation fiable dans des applications pratiques.
La recherche dichotomique est une méthode puissante pour trouver un élément dans un tableau trié. Son principe repose sur la comparaison de la valeur recherchée avec l'élément du milieu du tableau. Si la valeur est trouvée, l'algorithme s'arrête. Sinon, il continue la recherche dans la moitié gauche ou droite du tableau, selon que la valeur recherchée est plus petite ou plus grande.
Définition: La recherche dichotomique est un algorithme qui détermine la position d'un élément dans un tableau trié en divisant répétitivement la zone de recherche par deux.
L'implémentation en Python de cet algorithme de recherche dichotomique dans un tableau est présentée avec une fonction dichotomie(t, v) qui prend en paramètres le tableau t et la valeur recherchée v.
Exemple: Pour un tableau
t=, la fonction retournera 1 pourx=5et None pourx=90.
Le code Python utilise une boucle while et des variables gauche et droite pour délimiter la zone de recherche. À chaque itération, l'indice du milieu est calculé et comparé à la valeur recherchée.
Highlight: La complexité de la recherche dichotomique est logarithmique, ce qui la rend très efficace pour de grands ensembles de données triés.
Notre compagnon IA est spécialement conçu pour répondre aux besoins des étudiants. Sur la base des millions d'éléments de contenu que nous avons sur la plateforme, nous pouvons fournir des réponses vraiment significatives et pertinentes aux étudiants. Mais il ne s'agit pas seulement de réponses, le compagnon a encore plus pour but de guider les élèves dans leurs défis d'apprentissage quotidiens, avec des plans d'étude personnalisés, des quiz ou des éléments de contenu dans le chat et une personnalisation à 100% basée sur les compétences et les développements de l'étudiant.
Tu peux télécharger l'application dans Google Play Store et dans l'App Store d'Apple.
Oui, tu as un accès entièrement gratuit à tous les contenus de l'appli, tu peux chatter ou suivre les créateurs à tout moment. De plus, nous proposons Knowunity Premium, qui te permet de réviser sans limites!
App Store
Google Play
L'application est très facile d'utilisation et bien conçue. Jusqu'à présent, j'ai trouvé tout ce que je cherchais et j'ai pu apprendre beaucoup de choses grâce aux présentations ! Je vais certainement utiliser l'application pour un travail en classe ! Et comme source d'inspiration personnelle, elle est bien sûr aussi très utile.
Stefan S
utilisateur iOS
Cette application est vraiment super. Il y a tellement de fiches de révision et d'aide, [...]. Par exemple, la matière qui me pose problème est le français et l'appli a un choix d'aide très large. Grâce à cette application, je me suis améliorée en français. Je la recommanderais à tout le monde.
Samantha Klich
utilisatrice Android
Waouh, je suis vraiment abasourdi. J'ai essayé l'application parce que je l'avais déjà vue plusieurs fois dans la publicité et j'ai été absolument choquée. Cette appli est L'AIDE dont on rêve pour l'école et surtout, elle propose tellement de choses, comme des rédactions et des fiches qui m'ont personnellement TRÈS bien aidé.
Anna
utilisatrice iOS
Meilleur application je voulais m'entraîner pour mes maths puis j'ai tout compris d'un coup c'est mon nouveau prof maintenant 🤣🤣
Thomas R
utilisateur d' Android
super application pour réviser je révise tout les soirs
Esteban M
utilisateur d'Android
Permet de vraiment comprendre les cours sous forme de fiches de révisions déjà faites ! Incroyable, je recommande vraiment
Leny
utilisateur d'Android
L'application est tout simplement géniale ! Il me suffit de taper mon sujet dans la barre de recherche et je le vérifie très rapidement. Je ne dois plus regarder 10 vidéos YouTube pour comprendre quelque chose et j'économise ainsi mon temps. Je te le recommande !
Sudenaz Ocak
utilisateur Android
Cette application m'a vraiment fait m'améliorer ! J'étais vraiment nul en maths à l'école et grâce à l'appli, je suis meilleur en maths ! Je suis tellement reconnaissante que vous ayez créé cette application.
Greenlight Bonnie
utilisateur Android
PARFAIT 🌟 💕🔥 ça facilite Vrmt la révision avec des fiches de révisions fascinants✨🥰
Khady
utilisatrice d'Android
Je conseille vraiment ! je galère à avoir des cours clairs et ça aide énormément !!
Claire
utilisatrice iOS
C’est vraiment mais vraiment la meilleurs appli au début de l’année au collège jetait une élève perturbatrice et j’avais 9 de moyenne générale plus précisément 9,68... Et la un de mes potes me donne cette appli pour réviser c’était incroyable y’a des fiche de révision des quiz bref grâce à cette appli je suis passé de 9,68 à 17,40 trop contente 🤩🤩
Raoul
utilisateur IOS
Knowunity est vraiment une application incroyable elle est pour tous les âges et s’adapte à tous les niveaux.Elle permet de mieux comprendre et apprendre. Cette application est super pour les devoirs et pour les contrôles je la recommande à tous le monde petit ou grands
Ella
utilisatrice iOS
L'application est très facile d'utilisation et bien conçue. Jusqu'à présent, j'ai trouvé tout ce que je cherchais et j'ai pu apprendre beaucoup de choses grâce aux présentations ! Je vais certainement utiliser l'application pour un travail en classe ! Et comme source d'inspiration personnelle, elle est bien sûr aussi très utile.
Stefan S
utilisateur iOS
Cette application est vraiment super. Il y a tellement de fiches de révision et d'aide, [...]. Par exemple, la matière qui me pose problème est le français et l'appli a un choix d'aide très large. Grâce à cette application, je me suis améliorée en français. Je la recommanderais à tout le monde.
Samantha Klich
utilisatrice Android
Waouh, je suis vraiment abasourdi. J'ai essayé l'application parce que je l'avais déjà vue plusieurs fois dans la publicité et j'ai été absolument choquée. Cette appli est L'AIDE dont on rêve pour l'école et surtout, elle propose tellement de choses, comme des rédactions et des fiches qui m'ont personnellement TRÈS bien aidé.
Anna
utilisatrice iOS
Meilleur application je voulais m'entraîner pour mes maths puis j'ai tout compris d'un coup c'est mon nouveau prof maintenant 🤣🤣
Thomas R
utilisateur d' Android
super application pour réviser je révise tout les soirs
Esteban M
utilisateur d'Android
Permet de vraiment comprendre les cours sous forme de fiches de révisions déjà faites ! Incroyable, je recommande vraiment
Leny
utilisateur d'Android
L'application est tout simplement géniale ! Il me suffit de taper mon sujet dans la barre de recherche et je le vérifie très rapidement. Je ne dois plus regarder 10 vidéos YouTube pour comprendre quelque chose et j'économise ainsi mon temps. Je te le recommande !
Sudenaz Ocak
utilisateur Android
Cette application m'a vraiment fait m'améliorer ! J'étais vraiment nul en maths à l'école et grâce à l'appli, je suis meilleur en maths ! Je suis tellement reconnaissante que vous ayez créé cette application.
Greenlight Bonnie
utilisateur Android
PARFAIT 🌟 💕🔥 ça facilite Vrmt la révision avec des fiches de révisions fascinants✨🥰
Khady
utilisatrice d'Android
Je conseille vraiment ! je galère à avoir des cours clairs et ça aide énormément !!
Claire
utilisatrice iOS
C’est vraiment mais vraiment la meilleurs appli au début de l’année au collège jetait une élève perturbatrice et j’avais 9 de moyenne générale plus précisément 9,68... Et la un de mes potes me donne cette appli pour réviser c’était incroyable y’a des fiche de révision des quiz bref grâce à cette appli je suis passé de 9,68 à 17,40 trop contente 🤩🤩
Raoul
utilisateur IOS
Knowunity est vraiment une application incroyable elle est pour tous les âges et s’adapte à tous les niveaux.Elle permet de mieux comprendre et apprendre. Cette application est super pour les devoirs et pour les contrôles je la recommande à tous le monde petit ou grands
Ella
utilisatrice iOS
Chanel Lemaine
@chanizzle
La recherche dichotomiqueest un algorithme efficace pour trouver un élément dans un tableau trié. Elle divise répétitivement le tableau en deux, réduisant ainsi rapidement la zone de recherche. Cet algorithme est implémenté en Python et son fonctionnement, sa terminaison... Affiche plus
Accès à tous les documents
Améliore tes notes
Rejoins des millions d'étudiants
En t'inscrivant, tu acceptes les Conditions d'utilisation et la Politique de confidentialité.
La terminaison de l'algorithme de recherche dichotomique est cruciale pour garantir qu'il s'arrêtera toujours, quelle que soit l'entrée. Pour prouver la terminaison, on utilise le concept de variant de boucle.
Vocabulaire: Un variant de boucle est une valeur entière positive ou nulle qui décroît strictement à chaque itération de la boucle.
Dans le cas de la recherche dichotomique, le variant de boucle est la différence entre les indices droite et gauche. Cette valeur décroît strictement à chaque itération, assurant ainsi la terminaison de l'algorithme.
La correction de l'algorithme est démontrée en utilisant la technique de l'invariant de boucle. Un invariant de boucle est une proposition qui reste vraie à chaque itération.
Définition: Un invariant de boucle pour la recherche dichotomique est : "Si la valeur recherchée est dans le tableau, son indice est compris entre gauche et droite."
La démonstration de la correction montre que cet invariant reste vrai pour chacun des trois cas possibles à chaque itération : la valeur est trouvée, elle est dans la moitié gauche, ou elle est dans la moitié droite.
Highlight: La preuve de terminaison et de correction garantit que l'algorithme de recherche dichotomique fonctionne correctement et s'arrête toujours, ce qui est essentiel pour son utilisation fiable dans des applications pratiques.
Accès à tous les documents
Améliore tes notes
Rejoins des millions d'étudiants
En t'inscrivant, tu acceptes les Conditions d'utilisation et la Politique de confidentialité.
La recherche dichotomique est une méthode puissante pour trouver un élément dans un tableau trié. Son principe repose sur la comparaison de la valeur recherchée avec l'élément du milieu du tableau. Si la valeur est trouvée, l'algorithme s'arrête. Sinon, il continue la recherche dans la moitié gauche ou droite du tableau, selon que la valeur recherchée est plus petite ou plus grande.
Définition: La recherche dichotomique est un algorithme qui détermine la position d'un élément dans un tableau trié en divisant répétitivement la zone de recherche par deux.
L'implémentation en Python de cet algorithme de recherche dichotomique dans un tableau est présentée avec une fonction dichotomie(t, v) qui prend en paramètres le tableau t et la valeur recherchée v.
Exemple: Pour un tableau
t=, la fonction retournera 1 pourx=5et None pourx=90.
Le code Python utilise une boucle while et des variables gauche et droite pour délimiter la zone de recherche. À chaque itération, l'indice du milieu est calculé et comparé à la valeur recherchée.
Highlight: La complexité de la recherche dichotomique est logarithmique, ce qui la rend très efficace pour de grands ensembles de données triés.
Notre compagnon IA est spécialement conçu pour répondre aux besoins des étudiants. Sur la base des millions d'éléments de contenu que nous avons sur la plateforme, nous pouvons fournir des réponses vraiment significatives et pertinentes aux étudiants. Mais il ne s'agit pas seulement de réponses, le compagnon a encore plus pour but de guider les élèves dans leurs défis d'apprentissage quotidiens, avec des plans d'étude personnalisés, des quiz ou des éléments de contenu dans le chat et une personnalisation à 100% basée sur les compétences et les développements de l'étudiant.
Tu peux télécharger l'application dans Google Play Store et dans l'App Store d'Apple.
Oui, tu as un accès entièrement gratuit à tous les contenus de l'appli, tu peux chatter ou suivre les créateurs à tout moment. De plus, nous proposons Knowunity Premium, qui te permet de réviser sans limites!
Outils Intelligents NOUVEAU
Transforme cette fiche en : ✓ 50+ Questions d'Entraînement ✓ Cartes Mémoire Interactives ✓ Examen Blanc Complet ✓ Plans de Dissertation
App Store
Google Play
L'application est très facile d'utilisation et bien conçue. Jusqu'à présent, j'ai trouvé tout ce que je cherchais et j'ai pu apprendre beaucoup de choses grâce aux présentations ! Je vais certainement utiliser l'application pour un travail en classe ! Et comme source d'inspiration personnelle, elle est bien sûr aussi très utile.
Stefan S
utilisateur iOS
Cette application est vraiment super. Il y a tellement de fiches de révision et d'aide, [...]. Par exemple, la matière qui me pose problème est le français et l'appli a un choix d'aide très large. Grâce à cette application, je me suis améliorée en français. Je la recommanderais à tout le monde.
Samantha Klich
utilisatrice Android
Waouh, je suis vraiment abasourdi. J'ai essayé l'application parce que je l'avais déjà vue plusieurs fois dans la publicité et j'ai été absolument choquée. Cette appli est L'AIDE dont on rêve pour l'école et surtout, elle propose tellement de choses, comme des rédactions et des fiches qui m'ont personnellement TRÈS bien aidé.
Anna
utilisatrice iOS
Meilleur application je voulais m'entraîner pour mes maths puis j'ai tout compris d'un coup c'est mon nouveau prof maintenant 🤣🤣
Thomas R
utilisateur d' Android
super application pour réviser je révise tout les soirs
Esteban M
utilisateur d'Android
Permet de vraiment comprendre les cours sous forme de fiches de révisions déjà faites ! Incroyable, je recommande vraiment
Leny
utilisateur d'Android
L'application est tout simplement géniale ! Il me suffit de taper mon sujet dans la barre de recherche et je le vérifie très rapidement. Je ne dois plus regarder 10 vidéos YouTube pour comprendre quelque chose et j'économise ainsi mon temps. Je te le recommande !
Sudenaz Ocak
utilisateur Android
Cette application m'a vraiment fait m'améliorer ! J'étais vraiment nul en maths à l'école et grâce à l'appli, je suis meilleur en maths ! Je suis tellement reconnaissante que vous ayez créé cette application.
Greenlight Bonnie
utilisateur Android
PARFAIT 🌟 💕🔥 ça facilite Vrmt la révision avec des fiches de révisions fascinants✨🥰
Khady
utilisatrice d'Android
Je conseille vraiment ! je galère à avoir des cours clairs et ça aide énormément !!
Claire
utilisatrice iOS
C’est vraiment mais vraiment la meilleurs appli au début de l’année au collège jetait une élève perturbatrice et j’avais 9 de moyenne générale plus précisément 9,68... Et la un de mes potes me donne cette appli pour réviser c’était incroyable y’a des fiche de révision des quiz bref grâce à cette appli je suis passé de 9,68 à 17,40 trop contente 🤩🤩
Raoul
utilisateur IOS
Knowunity est vraiment une application incroyable elle est pour tous les âges et s’adapte à tous les niveaux.Elle permet de mieux comprendre et apprendre. Cette application est super pour les devoirs et pour les contrôles je la recommande à tous le monde petit ou grands
Ella
utilisatrice iOS
L'application est très facile d'utilisation et bien conçue. Jusqu'à présent, j'ai trouvé tout ce que je cherchais et j'ai pu apprendre beaucoup de choses grâce aux présentations ! Je vais certainement utiliser l'application pour un travail en classe ! Et comme source d'inspiration personnelle, elle est bien sûr aussi très utile.
Stefan S
utilisateur iOS
Cette application est vraiment super. Il y a tellement de fiches de révision et d'aide, [...]. Par exemple, la matière qui me pose problème est le français et l'appli a un choix d'aide très large. Grâce à cette application, je me suis améliorée en français. Je la recommanderais à tout le monde.
Samantha Klich
utilisatrice Android
Waouh, je suis vraiment abasourdi. J'ai essayé l'application parce que je l'avais déjà vue plusieurs fois dans la publicité et j'ai été absolument choquée. Cette appli est L'AIDE dont on rêve pour l'école et surtout, elle propose tellement de choses, comme des rédactions et des fiches qui m'ont personnellement TRÈS bien aidé.
Anna
utilisatrice iOS
Meilleur application je voulais m'entraîner pour mes maths puis j'ai tout compris d'un coup c'est mon nouveau prof maintenant 🤣🤣
Thomas R
utilisateur d' Android
super application pour réviser je révise tout les soirs
Esteban M
utilisateur d'Android
Permet de vraiment comprendre les cours sous forme de fiches de révisions déjà faites ! Incroyable, je recommande vraiment
Leny
utilisateur d'Android
L'application est tout simplement géniale ! Il me suffit de taper mon sujet dans la barre de recherche et je le vérifie très rapidement. Je ne dois plus regarder 10 vidéos YouTube pour comprendre quelque chose et j'économise ainsi mon temps. Je te le recommande !
Sudenaz Ocak
utilisateur Android
Cette application m'a vraiment fait m'améliorer ! J'étais vraiment nul en maths à l'école et grâce à l'appli, je suis meilleur en maths ! Je suis tellement reconnaissante que vous ayez créé cette application.
Greenlight Bonnie
utilisateur Android
PARFAIT 🌟 💕🔥 ça facilite Vrmt la révision avec des fiches de révisions fascinants✨🥰
Khady
utilisatrice d'Android
Je conseille vraiment ! je galère à avoir des cours clairs et ça aide énormément !!
Claire
utilisatrice iOS
C’est vraiment mais vraiment la meilleurs appli au début de l’année au collège jetait une élève perturbatrice et j’avais 9 de moyenne générale plus précisément 9,68... Et la un de mes potes me donne cette appli pour réviser c’était incroyable y’a des fiche de révision des quiz bref grâce à cette appli je suis passé de 9,68 à 17,40 trop contente 🤩🤩
Raoul
utilisateur IOS
Knowunity est vraiment une application incroyable elle est pour tous les âges et s’adapte à tous les niveaux.Elle permet de mieux comprendre et apprendre. Cette application est super pour les devoirs et pour les contrôles je la recommande à tous le monde petit ou grands
Ella
utilisatrice iOS
