>> Роб BOWDEN: Здраво, јас сум Роб.
Како ние да вработуваат бинарни пребарување?
Ајде да дознаете.
Така, имајте во предвид дека ова пребарување одиме за спроведување на рекурзивно.
Можете исто така би можеле да спроведат бинарни пребарување iteratively, па ако го направи тоа,
тоа е совршено добро.
>> Сега на прво место, ајде да се сетам што параметри за пребарување, се со цел да биде.
Тука, ние гледаме int вредност, која е би требало да биде вредноста на корисникот е
барате.
Можеме да видиме на int вредности низа, која е низа во која ние сме
во потрага по вредност.
И гледаме цел број n, која е времетраењето на нашите низа.
>> Сега, прво нешто што прво.
Ние се провери да се види дали N еднаква на 0, во кој случај ние се врати лажни.
Тоа е само велејќи, ако имаме празен низа, вредност не е јасно во
празна низа, така што може да се врати лажни.
>> Сега, ние всушност сакате да го направите бинарна Барај дел од бинарни пребарување.
Значи, ние сакаме да се најде на средината елемент на оваа низа.
Тука, ние се каже средината еднаква N поделени од 2, од средината елемент е
ќе биде должината на нашите низа поделено со 2.
Сега ние ќе треба да се провери да се види дали средината елемент е еднаква на вредноста ние сме
барате.
Па ако вредностите средината еднаква вредност, ние може да се врати точно бидејќи ние откривме
вредност во нашата низа.
>> Но, ако тоа не е вистина, сега ние треба да направите рекурзивен
чекор на бинарни пребарување.
Ние треба да се бараат или на лево од низа или до
средината на низата.
Па еве, ние се каже ако вредностите на средината е помалку од вредноста, што значи дека вредност
е поголема од средината на низата.
Значи вредност мора да биде на правото на елемент кој ние само погледна.
>> Па еве, ние ќе пребарување рекурзивно.
И ние ќе се погледне во она што го поминува тоа во вториот.
Но ние ќе се бара на правото на средината елемент.
И во другиот случај, тоа значи дека вредноста беше помала од средината на
низа, и така ние ќе за пребарување на лево.
Сега, по левата страна ќе биде малку полесно да се погледне.
Значи, гледаме дека тука сме рекурзивно повикувајќи пребарување каде што првиот
аргумент е, пак, вредноста ние сме во потрага завршена.
Вториот аргумент ќе биде низа што бевме во потрага завршена.
А последниот елемент сега е средината.
Се сеќавам на последниот параметар е нашата int n, па тоа е должината на нашите низа.
>> Во рекурзивен повик да се бараат, ние сме сега велат дека должината на
низа е средината.
Значи, ако нашите низа беше на големина 20 и пребаруваат на индекс 10, бидејќи средината е
20 поделено со 2, што значи дека ние сме кој поминува 10 како нови
должината на нашите низа.
Се сеќавам дека кога ќе имаат низа должина 10, тоа значи дека важи
елементи се во индекси од 0 до 9.
Значи ова е токму она што сакате да го наведете нашите ажурирани низа - по левата страна
низа од средината елемент.
>> Значи, во потрага на правото е малку потешко.
Сега на прво место, ајде да се разгледа должината на низата на правото на
средината елемент.
Значи, ако нашите низа беше на големина n, тогаш нова низа ќе биде на големина n минус
средината минус 1.
Значи, ајде да мислам на n минус средината.
>> Повторно, ако низата беа на големина 20 ние подели со 2 за да го добиете средината,
па средината е 10, тогаш n минус средината се случува да ни даде 10, па 10
елементи на правото на средината.
Но, ние исто така имаат оваа минус 1, бидејќи ние не сакаме да
вклучуваат средината себе.
Па n минус средината минус 1 нас дава вкупниот број на елементи на правото
на средината индекс во низа.
>> Сега тука, се сеќавам дека средината параметар е вредностите низа.
Па еве, ние сме полагање на нема вредности низа.
Ова вредности плус средината плус 1 е всушност се вели рекурзивно се јавите
пребарување, преминува во нова низа, каде дека нова низа започнува во средината
плус еден од нашите оригинални вредности низа.
>> Една алтернативна синтакса за тоа, сега дека сте почнале да ја видите покажувачи, е
симболот вредности средината плус 1.
Значи, го дофати адресата на средината плус еден елемент на вредности.
>> Сега, ако не беа удобно менување низа, како што,
исто така може да се спроведува оваа помош рекурзивен помошна функција, каде што
дека помошна функција се повеќе аргументи.
Така, наместо за преземање само на вредност, низа, а големината на низата,
помошник функција може да трае повеќе аргументи, вклучувајќи го и понизок индекс
кои ќе се грижат за во низа и горниот индекс, кој ти е гајле
за низа.
>> И така следење на двете пониски индекс и горниот индекс, вие не
треба да некогаш менување на оригинални вредности низа.
Можете едноставно да продолжите да користете вредности низа.
Но, тука, информации ние не треба помошник функционираат како долго како што се
подготвени за менување на оригиналниот вредности низа.
Ние сме подготвени да се помине во ажурирани вредности.
>> Сега, ние не може бинарни пребарување над низа што е вон.
Значи, ајде да добиете оваа решат.
Сега, да се забележи дека вид е изминатите две параметри int вредности, кое е
низа, дека ние сме сортирање и int n, кое е должината на низа која
ние сме сортирање.
Значи, тука сакаме да се имплементира на сортирање алгоритам
што е o на n квадрат.
Можете да изберете меур вид, селекција вид, или вметнување вид, или
некои други вид немаме виден во класата.
Но, овде, ние ќе го користите селекција вид.
>> Значи, ние ќе iterate во текот на целата низа.
Добро, тука можеме да видиме дека ние сме процесирањето од 0 до n минус 1.
Зошто не сите на патот до n?
Па, ако веќе сме подредени на првиот n минус 1 елементи, тогаш
Многу последниот елемент што веќе мора да биде во правилната место, па сортирање над
целата низа.
>> Сега, се сеќавам како избор вид работи.
Ние ќе одиме во текот на целата низа во потрага по минималната вредност во
низа и стап кој на почетокот.
Тогаш ние ќе одиме во текот на целиот низа повторно во потрага по втората
најмалиот елемент, и стап кој во втората позиција во
низа, и така натаму.
Значи, тоа е она што овој го прави.
>> Тука, ние сме сведоци дека ние сме поставување на тековната минимум
вредност на i-тиот индекс.
Па на првата итерација, ние ќе да се разгледа на минималната вредност да биде
почетокот на нашата низа.
Тогаш, ние ќе iterate преку остатокот од низата, проверка за да
види дали има било какви елементи помали од оној што ние сме во моментов
со оглед на минимум.
>> Па еве, вредности ѕ плус еден - тоа е помалку од она што ние сме во моментов
со оглед на минимум.
Тогаш ние ќе треба да се ажурира што мислиме дека е минимум за да
индекс ѕ плус 1.
Значи, го направи тоа низ целата низа, и по овој за телефонска линија, минимум
треба да биде минимално елемент од позицијата i-тиот во низа.
>> Откако ќе го имаме тоа, ние може да се трампа на минималната вредност во I-та позиција
во низа.
Па ова е само стандарден swap.
Ние се сместат во привремени вредност - i-тиот вредност во низа -
стави во i-тиот вредност во низа на минималната вредност која припаѓа таму,
а потоа да се сместат назад во која тековните минимална вредност се користи за да биде
i-тиот вредност во низа, така дека ние не го изгуби.
>> Значи, кој го продолжува следниот повторување.
Ќе почнете да барате вториот минималната вредност и вметнете дека во
втората позиција.
На третиот повторување, ние ќе се погледне за третиот минималната вредност и вметнете
дека во третата позиција, и така се додека имаме сортирани низа.
Моето име е Роб, и ова беше изборот вид.