ROB BOWDEN: Salut, je suis Rob. Comment nous employons faire une recherche binaire? Voyons. Donc, notez que cette recherche nous allons à mettre en oeuvre de manière récursive. Vous pouvez également mettre en œuvre une recherche binaire itérative, donc si vous l'avez fait, c'est tout à fait correct. 

Maintenant abord, rappelons ce que le paramètres de recherche sont censés être. Ici, nous voyons la valeur int, ce qui est censé être la valeur que l'utilisateur est chercher. Nous voyons les valeurs int tableau, ce qui est la matrice dans laquelle nous sommes la recherche de valeur. Et nous voyons int n, qui est la longueur de notre réseau. 

Maintenant, la première chose que le premier. Nous vérifions pour voir si n est égal à 0, dans auquel cas l'on retourne faux. C'est tout simplement dire que si nous avons un vide array, value n'est clairement pas dans un tableau vide, afin que nous puissions retourner false. 

Maintenant, nous voulons vraiment faire le binaire Recherche partie de la recherche binaire. Donc, nous voulons trouver le milieu élément de ce tableau. Ici, nous disons milieu égale n divisé par deux, étant donné que l'élément intermédiaire est va être la longueur d' notre tableau divisé par 2. Maintenant, nous allons vérifier pour voir si le élément central est égale à la valeur que nous sommes chercher. Donc, si les valeurs moyenne égale valeur, nous peut retourner vrai que nous avons trouvé l' valeur dans notre tableau. 

Mais si ce n'était pas vrai, maintenant nous devons faire la récursif étape de recherche binaire. Nous devons chercher soit à l' à gauche de la matrice ou à l' milieu de la rangée. Donc, ici, nous disons si les valeurs de milieu est moins de valeur, ce qui signifie que la valeur est supérieure à la moyenne de la matrice. Donc, la valeur doit être à droite de la élément que nous venons d'examiner. 

Donc, ici, nous allons rechercher de manière récursive. Et nous allons voir ce que nous passons pour cela d'une seconde. Mais nous allons chercher à l' droit de l'élément intermédiaire. Et dans l'autre cas, cela signifie que la valeur était inférieure à la moyenne de l' tableau, et ainsi nous allons à la recherche à la gauche. Maintenant, la gauche va être un peu plus facile à regarder. Ainsi, nous voyons ici que nous sommes de façon récursive appelant la recherche où la première argument est, à nouveau, la valeur nous sommes à la recherche sur. Le deuxième argument est va être la tableau que nous cherchions sur. Et le dernier élément est maintenant milieu. Rappelez-vous le dernier paramètre est notre int n, de sorte que c'est la longueur de notre réseau. 

Dans l'appel récursif à la recherche, nous sommes maintenant dire que la longueur de l' tableau est moyenne. Donc, si notre tableau était d'une taille 20 et nous recherché à l'indice 10, depuis la mi-est 20 divisé par 2, cela signifie que nous sommes passant de 10 en tant que nouveau longueur de notre réseau. N'oubliez pas que lorsque vous avez un tableau longueur de 10, cela signifie que la validité les éléments sont des indices de 0 à 9. Donc, c'est exactement ce que nous voulons indiquer notre tableau mis à jour - la gauche tableau à partir de l'élément intermédiaire. 

Ainsi, en regardant vers la droite est un peu plus difficile. Maintenant abord, nous allons examiner la longueur de la matrice vers la droite de l' élément central. Donc, si notre tableau était de taille n, alors la nouveau tableau sera de taille n moins moins milieu 1. Donc, nous allons penser à n moins moyenne. 

Encore une fois, si le tableau était de la taille 20 et nous divisons par 2 pour obtenir la moyenne, de sorte que le milieu est 10, n moins milieu va nous donner 10, donc 10 éléments à droite du milieu. Mais nous avons aussi ce moins 1, puisque nous ne voulons pas inclure le milieu lui-même. Alors n moins milieu moins 1 nous donne la nombre total d'éléments vers la droite de l'indice du milieu dans le tableau. 

Maintenant ici, n'oubliez pas que le milieu paramètre est le tableau des valeurs. Donc, ici, nous passons une mise à jour des valeurs tableau. Ces valeurs plus plus milieu 1 est fait dire appeler de façon récursive recherche, en passant dans un nouveau tableau, où cette nouvelle gamme commence au milieu plus une origine de notre tableau de valeurs. 

Une syntaxe alternative pour que, maintenant que vous avez commencé à voir des pointeurs, est valeurs esperluette, plus milieu 1. Alors, prenez l'adresse du milieu plus un élément de valeurs. 

Maintenant, si vous n'étiez pas à l'aise modification d'un tableau comme ça, vous pourrait également avoir mis en œuvre cette aide une fonction d'assistance récursive, où que fonction d'assistance prend plusieurs arguments. Ainsi, au lieu de prendre simplement la valeur, la matrice, et la taille de la matrice, la fonction d'assistance pourrait prendre plus arguments, y compris l'indice inférieur que vous vous souciez de la matrice et l'indice supérieur que vous vous souciez sur le tableau. 

Et ainsi garder la trace de deux bas indice et l'indice supérieure, vous ne doivent jamais modifier le valeurs initiales tableau. Vous pouvez tout simplement continuer à utiliser le tableau de valeurs. Mais ici, remarquons que nous n'avons pas besoin d'une aide fonctionner aussi longtemps que nous sommes prêt à modifier l'original valeurs tableau. Nous sommes prêts à passer à un valeurs mises à jour. 

Maintenant, nous ne pouvons pas la recherche binaire sur un tableau non trié. Donc, nous allons obtenir ce triés. Maintenant, remarquez ce genre est passé de deux int valeurs des paramètres, qui est le tableau que nous le tri, et int n, qui est la longueur du réseau que nous le tri. Donc, ici, nous voulons mettre en œuvre un algorithme de tri c'est o n carré. Vous pouvez choisir bulle tri, la sélection tri ou le tri par insertion, ou une autre sorte que nous n'avons pas vu en classe. Mais ici, nous allons utiliser la sélection sorte. 

Donc, nous allons parcourir sur l'ensemble du réseau. Eh bien, ici nous voyons que nous sommes itération de 0 à n moins 1. Pourquoi ne pas tout le chemin jusqu'à n? Eh bien, si nous avons déjà trié la première n moins 1 éléments, puis le dernier élément qui doit déjà être au bon endroit, si le tri sur l'ensemble du réseau. 

Maintenant, rappelez-vous comment la sélection travaux de tri. Nous allons passer en revue l'ensemble du réseau la recherche de la valeur minimum dans la matrice et le bâton que au début. Ensuite, nous allons passer en revue l'ensemble du tableau à nouveau à la recherche de la deuxième plus petit élément, et le bâton que dans la deuxième position dans la tableau, et ainsi de suite. Donc, c'est ce que ce fait. 

Ici, nous voyons que nous sommes réglage du minimum actuel La valeur de l'indice i-ième. Ainsi, sur la première itération, nous allons de considérer la valeur minimum pour être le début de notre tableau. Ensuite, nous allons parcourir la reste de la matrice, en contrôlant voir s'il ya des éléments plus petits que celle que nous sommes actuellement compte tenu du minimum. 

Donc, ici, les valeurs j plus un - c'est moins que ce que nous sommes actuellement compte tenu du minimum. Ensuite, nous allons mettre à jour ce nous pensons que c'est le minimum à indice j + 1. Alors, le faire à travers l'ensemble du réseau, et après cette boucle, minimum doit être au minimum de l'élément la position de la i-ème dans le tableau. 

Une fois que nous avons, nous pouvons échanger l' valeur minimale dans la position i-ième dans le tableau. Donc, c'est juste un échange standard. Nous conservons une valeur temporaire - la valeur de la i-ème dans le tableau - la mise en valeur de la i-ème dans le tableau de la valeur minimale qui appartient là, puis stocker en retour d'où la valeur minimale de courant utilisé pour la i-ième valeur dans le tableau, de sorte que que nous n'avons pas le perdre. 

Alors, qui continue sur l'itération suivante. Nous allons commencer la recherche de la deuxième valeur minimale et l'insérer dans le seconde position. Sur la troisième itération, nous chercherons la valeur minimale et la troisième pièce rapportée que dans la troisième position, et ainsi jusqu'à ce que nous avons un tableau trié. Mon nom est Rob, et ce était la sélection sorte.