>> ROB BOWDEN: Здравейте, аз съм на Роб.
Как ние използваме двоично търсене?
Нека разберем.
Така че, имайте предвид, че това търсене отиваме да прилагат рекурсивно.
Вие също може да изпълнява двоично търсене итеративно, така че ако го направи,
това е съвършено глоба.
>> Сега на първо място, нека си припомним какво по параметри за търсене са предназначени да бъдат.
Ето, ние виждаме, Int стойност, която е Предполага се, че стойността на потребителя е
търси.
Виждаме масив вътр ценности, които е масив, в който сме
търси за стойност.
И ние виждаме Int N, която е дължината на нашия масив.
>> Сега, първото нещо, което на първо място.
Ние проверяваме дали N е равно на 0, в който случай ние връщане фалшиви.
Това е просто казвам, ако имаме един празен масив, стойност ясно не е в
празен масив, така че ние може да се върне фалшиви.
>> Сега, ние всъщност искаме да направим двоичен търсене част от двоично търсене.
Така че, ние искаме да се намери средата елемент на този масив.
Ето, ние казваме, средната равнява н разделена от 2, тъй като средната елемент е
ще бъде дължината на ни масив разделен от 2.
Сега отиваме да се провери, за да видите, ако средния елемент е равна на стойността сме
търси.
Така че, ако стойностите на средната стойност се равнява, ние може да се върне вярно, тъй като ние открихме, че
стойност в нашия масив.
>> Но ако това не е вярно, сега ние трябва да направим на рекурсивния
стъпка на двоично търсене.
Ние трябва да се търси или към оставен на масива или на
средата на масива.
Така че тук, ние казваме, ако стойностите на средно е по-малко от стойността, това означава, че стойността
е по-голяма от средната на масива.
Така че стойността трябва да бъде правото на елемент, който ние просто погледна.
>> Така че тук, ние ще търси рекурсивно.
И ние ще разгледаме това, което минава на това в секунда.
Но ние ще се търсенето на територията на право на средния елемент.
А в другия случай, това означава, че стойност е по-малко, отколкото в средата на
масив, и така отиваме да намерите в ляво.
Сега, в ляво ще бъде малко по-лесно за гледане.
Така че, ние виждаме тук, че ние сме рекурсивно призовава за търсене, където на първия
аргумент е, отново, стойността търсим свърши.
Вторият аргумент, ще бъде масив, който ние търсехме свърши.
И последният елемент в момента е в средата.
Запомни последния параметър е нашата Int N, така че е дължината на нашия масив.
>> В рекурсивно повикване да търсите, ние сме Сега казва, че дължината на
масив е средна.
Така че, ако нашият масив е с размер 20 и ние търси с индекс 10, тъй като средата е
20, разделено на две, това означава, че ние сме прокарате 10 като новия
дължина на нашия масив.
Не забравяйте, че когато имаш масив с дължина 10, това означава, че валидните
елементи са в индекси от 0 до 9.
Така че това е точно това, което искаме да уточни актуализира нашия масив - ляво
масив от средния елемент.
>> Така, гледащ надясно е малко по-трудно.
Сега на първо място, нека да разгледаме дължината на масива до правото на
среден елемент.
Така че, ако нашият масив е с размер N, тогава Новата гама ще бъде с размер N минус
средна минус 1.
Така че, нека да мислим за п минус средната.
>> Отново, ако масива са с размер 20 и ние разделяме с 2, за да получите по средата,
така че средата е 10, тогава п минус средната ще ни даде 10, така че 10
елементи от правото на средата.
Но ние също имаме този минус 1, тъй като ние не искаме да
включват се средата.
Така п минус средната минус едно ни е дава общия брой на елементи на правото
на средния индекс в масива.
>> Сега тук, не забравяйте, че по средата параметър е масив стойности.
Така че тук, ние сме полагане на актуализиран стойности масив.
Тези стойности плюс средната плюс едно е всъщност казва рекурсивно обадите
търсене, преминавайки в нов масив, където този нов масив започва в средата
плюс един от нашите оригинални стойности масив.
>> Един алтернативен синтаксис за това, че сега сте започнали да виждате указатели, е
амперсанд стойности средната плюс един.
Така че, вземете адреса на центъра плюс един елемент от ценности.
>> Сега, ако не беше удобно модифициране масив като че ли
също може да са приложили това, като използвате функция рекурсивен помощник, когато
че помощник функция може да отнеме повече аргументи.
Така че вместо да вземе точно е стойността, масив, и размера на масива,
функцията на помощник може да отнеме повече аргументи, включително по-нисък индекс
, че ще се грижи за в масива и горната индексът, който ви интересува
за масива.
>> И така следене както на по-ниската индекс и горната индекса, не знаеш
трябва някога да модифицирате първоначалните стойности на масив.
Можете просто да продължите да използват масива стойности.
Но тук, забележете, ние не се нуждаят от помощник функционира толкова дълго, колкото ние сме
готови за промяна на оригинала стойности масив.
Ние сме готови да преминат в обновения ценности.
>> Сега, ние не можем двоично търсене в над масив, който е сортиран.
Така че, нека да получите това, подредени.
Сега забелязвам, че нещо като е минало два параметри INT стойности, който е
масив, който ние сме сортиране и Int N, което е дължината на масива, че
ние сме сортиране.
Така че, тук искаме да се приложат един алгоритъм за сортиране
че е о п квадрат.
Можете да изберете балон сортиране, подбор сортиране, или вмъкване вид, или
някакъв друг вид ние не трябва вижда в клас.
Но тук, ние ще използвате избор на сортиране.
>> Така че, ние отиваме да превъртите за цялата решетка.
Е, тук виждаме, че ние сме итерации от 0 до п минус 1.
Защо не целия път до п?
Е, ако вече сме подредени на първия N минус 1 елементи, тогава
последния елемент, което трябва вече да в правилното място, така сортиране през
целият масив.
>> Сега си спомням как селекция подреди работи.
Отиваме да отиде за цялата решетка, търси минималната стойност в
масива и тоягата, че в началото.
Тогава ние ще тръгнем по цялата масив отново търси за втори
Най-малкият елемент, и пръчка, че през втората позиция в
масив, и така нататък.
Така че, това е, което това се прави.
>> Ето, ние виждаме, че сме определяне на текущия минимум
стойност на I-ия индекс.
Така на първата итерация, отиваме да разгледа минималната стойност е
началото на нашия масив.
След това, ние ще обхождане на остатък на масива, като се проверяват за
да видим дали има някакви елементи, по-малки от този, който в момента сме
това минимум.
>> Така че тук, ценности J плюс един - това е по-малко от това, което сме в момента
това минимум.
След това ние ще се актуализира какво ние мислим, е минимумът, за да
индекс J плюс един.
Така че, направи това през целия масив, и след това в продължение на контур, минимално
трябва да бъде минимум елемент от I-та позиция в масива.
>> След като имаме това, ние можем да сменяте минимална стойност в позиция I-та
в масива.
Така че това е просто стандартна суап.
Ние съхраняваме във временно стойност - стойността на I-та в масива -
пусната в стойността на I-то място в масива Минималната стойност, която принадлежи там,
и след това се съхранява в гърба, където сегашната минимална стойност използвани за да бъде
I-та стойност в масива, така че ние не го загубим.
>> Така, че продължава следващата итерация.
Ще започнете да търсите за секунди минимална стойност и го поставете, че в
втора позиция.
На третата итерация, ние ще разгледаме за третата минималната стойност и вложка
че в трета позиция, и така докато имаме сортиран масив.
Моето име е Роб, и това е избор на сортиране.