summaryrefslogtreecommitdiffhomepage
path: root/fr-fr/binary-search-fr.html.markdown
diff options
context:
space:
mode:
authorhyphz <drmoose94@gmail.com>2017-07-18 17:56:42 +0100
committerhyphz <drmoose94@gmail.com>2017-07-18 17:56:42 +0100
commit5ab5cb9800822d607be2c6ac943377811db98158 (patch)
tree3c804707822744c20da1de54ff60fc8c3197781b /fr-fr/binary-search-fr.html.markdown
parent62102d02992f83b3a1fb745a39f36332dd4435b7 (diff)
parent6e7c5c793327f4a63b13e555894597915ca91fda (diff)
Merge remote-tracking branch 'adambard/master'
Diffstat (limited to 'fr-fr/binary-search-fr.html.markdown')
-rw-r--r--fr-fr/binary-search-fr.html.markdown67
1 files changed, 67 insertions, 0 deletions
diff --git a/fr-fr/binary-search-fr.html.markdown b/fr-fr/binary-search-fr.html.markdown
new file mode 100644
index 00000000..4c34da0f
--- /dev/null
+++ b/fr-fr/binary-search-fr.html.markdown
@@ -0,0 +1,67 @@
+---
+category: Algorithms & Data Structures
+name: Binary Search
+contributors:
+ - ["Abhishek Jaisingh", "http://github.com/abhishekjiitr"]
+translators:
+ - ["Hughes Perreault", "https://github.com/hperreault"]
+lang: fr-fr
+---
+
+# Recherche Binaire
+
+## Pourquoi la Recherche Binaire ?
+
+La recherche est un des principaux problèmes dans le domaine de l'informatique. De nos jours, il y a plus de 1 milliard de recherches par année, et nous avons besoin d'algorithmes pour faire cela rapidement. La recherche binaire est un des algorithmes les plus fondamentaux en informatique. Pour pouvoir l'explorer en détail, nous allons d'abord établir une base théorique, puis nous allons utiliser cette base pour implémenter l'algorithme en soi.
+
+## Introduction
+
+Une façon simple d'implémenter la recherche est de faire une recherche linéaire. Cependant, cette approche prend beaucoup de temps, et ce temps augmente linéairement avec la quantité de données. Par exemple, partons du premier élément d'un tableau t[], et un par un, comparons x avec chaque élément de t[]. Si x est égal à un élément, nous retournons l'index, si x n'égale aucun élément, nous retournons -1.
+
+```
+Recherche Linéaire: O (n) Temps Linéaire
+
+Recherche Binaire: O ( log(n) ) Temps Logarithmique
+
+```
+```
+def search(arr, x):
+
+ for i in range(len(arr)):
+
+ if arr[i] == x:
+ return i
+
+ return -1
+
+```
+## L'Algorithme de Recherche Binaire
+
+Le prérequis fondamental de la recherche binaire est que les éléments soient triés.
+
+### Algo
+
+```
+L'idée derrière la recherche binaire est d'utiliser le fait que le tableau est trié afin de réduire la complexité à O(Log(n)). Nous pouvons ignorer la moitié des éléments après la première comparaison.
+1) Comparons x avec l'élément du milieu.
+2) Si x est égal à cet élément, nous retournons l'index du milieu.
+3) Sinon, si x est plus grand que l'élément du milieu, alors x peut seulement être dans la dernière moitié du tableau. Donc, nous recommençons la procédure avec cette dernière moitié.
+4) Sinon (x est plus petit), nous recommençons la procédure avec la première moitié du tableau.
+Ensuite nous avons une implémentation récursive de la recherche binaire.
+
+```
+
+### Note de la fin
+
+Partie en construction.
+
+## Livre
+
+* [CLRS EN](https://mitpress.mit.edu/books/introduction-algorithms)
+* [Algorithmes EN](http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X)
+* [Design d'Algorithmes EN](http://www.amazon.com/Algorithm-Design-Foundations-Analysis-Internet/dp/0471383651)
+
+## Ressources en ligne
+
+* [GeeksforGeeks EN](http://www.geeksforgeeks.org/the-ubiquitous-binary-search-set-1/)
+* [Topcoder Tutorial EN](https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/)