[Powered by Google Translate] [ביינערי זוך] [פּאַטריק שמיד - האַרוואַרד אוניווערסיטעט] [דאס איז קס50. - CS50.TV] 

אויב איך געגעבן איר אַ רשימה פון דיסניי כאַראַקטער נעמען אין אַלפאַבעטיקאַל סדר און געבעטן איר צו געפֿינען מיקי מויז, ווי וואָלט איר גיין וועגן טאן דעם? מען קלאָר ווי דער טאָג וועג וואָלט זייַן צו יבערקוקן דער רשימה פון די אָנהייב און טשעק יעדער נאָמען צו זען אויב עס ס מיקי. אבער ווי איר לייענען אַלאַדדין, אַליס, אריאל, און אַזוי אַרויס, איר וועט געשווינד פאַרשטיין אַז סטאַרטינג אין די פראָנט פון די רשימה איז ניט אַ גוט געדאַנק. אָוקיי, אפֿשר איר זאָל אָנהייבן ארבעטן קאַפּויער פון די סוף פון די רשימה. איצט איר לייענען טאַרזאַן, סטיטטש, שניי ווייסע, און אַזוי אַרויס. נאָך, דאָס טוט נישט ויסקומען ווי דער בעסטער וועג צו גיין וועגן אים. 

נו, אן אנדער וועג אַז איר קען גיין וועגן טאן דאָס איז צו פּרובירן צו שמאָל אַראָפּ די רשימה פון נעמען וואָס איר האָט צו קוקן בייַ. זינט איר וויסן אַז זיי זענען אין אַלפאַבעטיקאַל סדר, איר קען נאָר קוק אין די נעמען אין די מיטל פון דער רשימה און טשעק אויב מיקי מאַוס איז פאר אָדער נאָך דעם נאָמען. קוקן אין די לעצטע נאָמען אין די רגע זייַל איר 'ד פאַרשטיין אַז ב פֿאַר מיקי קומט נאָך דזש פֿאַר דזשאַסמינע, אַזוי איר 'ד פשוט איגנאָרירן די ערשטער העלפט פון די רשימה. דעמאָלט איר 'ד מיסטאָמע קוקן בייַ די שפּיץ פון די לעצטע זייַל און זען אַז עס הייבט מיט ראַפּונזעל. מיקי קומט איידער ראַפּונזעל; קוקט ווי מיר קענען איגנאָרירן די לעצטע זייַל ווי געזונט. ממשיך די זוכן סטראַטעגיע, איר וועט אינגיכן זען אַז מיקי איז אין דער ערשטער העלפט פון די רוען רשימה פון נעמען און לעסאָף געפֿינען מיקי כיידינג צווישן מערלין און מיני. 

וואָס איר נאָר האבן האט בייסיקלי ביינערי זוכן. ווי דעם נאָמען ימפּלייז, עס פּערפאָרמז זייַן שאַרף סטראַטעגיע אין אַ ביינערי ענין. וואָס טוט דאָס מיינען? נו, געגעבן אַ רשימה פון אויסגעשטעלט זאכן, די ביינערי זוכן אַלגערידאַם מאכט אַ ביינערי באַשלוס - לינקס אָדער רעכט, גרעסער ווי אָדער ווייניקער ווי, אַלפאַבעטיקלי פאר אָדער נאָך - בייַ יעדער פונט. איצט אַז מיר האָבן אַ נאָמען וואָס גייט צוזאמען מיט דעם זוכן אַלגערידאַם, לאָזן ס קוק בייַ אן אנדער בייַשפּיל, אָבער דאָס מאָל מיט אַ רשימה פון אויסגעשטעלט נומערן. זאָגן מיר זענען קוקן פֿאַר דעם נומער 144 אין דעם רשימה פון אויסגעשטעלט נומערן. פּונקט ווי פריער, מיר געפֿינען די נומער וואָס ס אין די מיטל - וואָס אין דעם פאַל איז 13 - און זען אויב 144 איז גרעסער ווי אָדער ווייניקער ווי 13. זינט עס ס קלאר גרעסער ווי 13, מיר קענען איגנאָרירן אַלץ וואָס איז 13 אָדער ווייניקער און נאָר קאַנסאַנטרייט אויף די רוען האַלב. זינט מיר איצט האָבן אַן אַפֿילו נומער פון זאכן לינקס, מיר פשוט קלייַבן אַ נומער וואָס איז נאָענט צו די מיטל. אין דעם פאַל מיר קלייַבן 55. מיר קען האָבן נאָר ווי לייכט אויסדערוויילט 89. אָוקיי. ווידער, 144 איז גרעסער ווי 55, אַזוי מיר גיין צו די רעכט. גליק פֿאַר אונדז, דער ווייַטער מיטן נומער איז 144, דער איינער מיר רע קוקן פֿאַר. אַזוי אין סדר צו געפֿינען 144 ניצן אַ ביינערי זוכן, מיר רע קענען צו געפֿינען עס אין בלויז 3 טריט. אויב מיר וואָלט האָבן געניצט לינעאַר זוכן דאָ, עס וואָלט האָבן גענומען אונדז 12 טריט. ווי אַ ענין פון פאַקט, זינט דעם זוכן אופֿן כאַווז די נומער פון זאכן עס האט צו קוקן בייַ בייַ יעדער שריט, עס וועט געפֿינען די נומער עס איז שאַרף פֿאַר אין וועגן די קלאָץ פון די נומער פון זאכן אין דער רשימה. איצט אַז מיר ווע געזען 2 ביישפילן, לאָזן ס נעמען אַ קוק בייַ עטלעכע פּסעודאָקאָדע פֿאַר אַ רעקורסיווע פונקציאָנירן אַז ימפּלאַמאַנץ ביינערי זוכן. סטאַרטינג בייַ די שפּיץ, מיר זען וואָס מיר האָבן צו געפֿינען אַ פֿונקציע וואָס נעמט 4 טענות: שליסל, מענגע, מין, און מאַקס. דער שליסל איז די נומער וואָס מיר זענען קוקן פֿאַר, אַזוי 144 אין די פֿריִערדיקע בייַשפּיל. מענגע איז די רשימה פון נומערן וואָס מיר זענען שאַרף. מין און מאַקס זענען די ינדיסעס פון די מינימום און מאַקסימום שטעלעס אַז מיר זענען דערווייַל קוקן בייַ. אַזוי ווען מיר אָנהייבן, מין וועט זייַן נול און מאַקס וועט זייַן די מאַקסימום אינדעקס פון דער מענגע. ווי מיר שמאָל די זוכן אַראָפּ, מיר וועלן דערהייַנטיקן מין און מאַקס צו זייַן נאָר די קייט אַז מיר זענען נאָך קוקן ין 

זאל ס האָפּקען צו די טשיקאַווע טייל ערשטער. דער ערשטער זאַך מיר טאָן איז געפֿינען די מידפּוינט, די אינדעקס וואָס איז אַפנ האַלבנ וועג צווישן דעם מין און מאַקס פון די מענגע אַז מיר זענען נאָך קאָנסידערינג. דעמאָלט מיר קוקן אין די ווערט פון די מענגע בייַ אַז מידפּוינט אָרט און זען אויב די נומער וואָס מיר זענען קוקן פֿאַר איז ווייניקער ווי אַז שליסל. אויב די נומער בייַ אַז שטעלע איז ווייניקער, דעמאָלט עס מיטל דער שליסל איז גרעסערע ווי אַלע נומערן צו די לינקס פון וואָס שטעלע. אַזוי מיר קענען רופן ביינערי זוכן פונקציאָנירן ווידער, אָבער דאָס מאָל אַפּדייטינג דעם מין און מאַקס פּאַראַמעטערס צו לייענען נאָר די האַלב וואָס איז גרעסער ווי אָדער גלייַך צו דער ווערט מיר נאָר געקוקט בייַ. אויף די אנדערע האַנט, אויב דער שליסל איז ווייניקער ווי די נומער בייַ די קראַנט מידפּוינט פון די מענגע, מיר וועלן צו גיין צו די לינקס און איגנאָרירן אַלע נומערן וואָס זענען גרעסער. ווידער, מיר רופן ביינערי זוכן אָבער דאָס מאָל מיט די קייט פון מין און מאַקס דערהייַנטיקט צו אַרייַננעמען נאָר דער נידעריקער האַלב. אויב די ווערט בייַ די קראַנט מידפּוינט אין די מענגע איז ניט גרעסערע ווי אדער קלענערער ווי די שליסל, דעמאָלט עס מוזן זייַן גלייַך צו די שליסל. אזוי, מיר קענען פשוט צוריקקומען די קראַנט מידפּוינט אינדעקס, און מיר רע געטאן. צום סוף, דעם טשעק דאָ איז פֿאַר די פאַל אַז די נומער איז נישט פאקטיש אין די מענגע פון ​​נומערן מיר זענען שאַרף. אויב די מאַקסימום אינדעקס פון דער קייט וואָס מיר זענען קוקן פֿאַר איז אלץ ווייניקער ווי דעם מינימום, אַז מיטל אַז מיר ווע ניטאָ אויך ווייַט. זינט די נומער איז נישט אין די אַרייַנשרייַב מענגע, מיר צוריקקומען -1 צו אָנווייַזן אַז גאָרנישט איז געפונען. 

איר זאלט ​​האָבן באמערקט אַז פֿאַר דעם אַלגערידאַם צו אַרבעטן, די רשימה פון נומערן האט צו זייַן אויסגעשטעלט. אין אנדערע ווערטער, מיר קענען נאָר געפֿינען 144 ניצן ביינערי זוכן אויב אַלע די נומערן זענען באפוילן פון לאָואַסט צו העכסטן. אויב דאָס זענען נישט דער פאַל, מיר וואָלט ניט זייַן ביכולת צו ויסשליסן האַלב פון די נומערן אין יעדער שריט. אַזוי מיר האָבן 2 אָפּציעס. אָדער מיר קענען נעמען אַ ונסאָרטעד רשימה און סאָרט עס איידער ניצן ביינערי זוכן, אָדער מיר קענען מאַכן זיכער אַז די רשימה פון נומערן איז אויסגעשטעלט ווי מיר לייגן נומערן צו עס. אזוי, אַנשטאָט פון סאָרטינג פּונקט ווען מיר האָבן צו זוכן, וואָס ניט האַלטן די רשימה אויסגעשטעלט בייַ אַלע מאל? 

איין וועג צו האַלטן אַ רשימה פון נומערן אויסגעשטעלט בשעת סיימאַלטייניאַסלי אַלאַוינג איין צו לייגן אָדער מאַך נומערן פון דעם רשימה איז דורך ניצן עפּעס גערופן אַ ביינערי זוכן בוים. א ביינערי זוכן בוים איז אַ דאַטן סטרוקטור וואָס האט 3 פּראָפּערטיעס. ערשטער, די לינקס סובטרעע פון ​​קיין נאָדע כּולל בלויז וואַלועס וואָס זענען ווייניקער ווי אָדער גלייַך צו די נאָדע ס ווערט. רגע, די רעכט סובטרעע פון ​​אַ נאָדע נאָר כּולל וואַלועס וואָס זענען גרעסער ווי אָדער גלייַך צו די נאָדע ס ווערט. און, ענדלעך, ביידע די לינק און רעכט סובטרעעס פון אַלע נאָודז ביסט אויך ביינערי זוכן ביימער. זאל ס קוק בייַ אַ בייַשפּיל מיט די זעלבע נומערן מיר געניצט פריער. פֿאַר יענע פון ​​איר וואס האָבן קיינמאָל געזען אַ קאָמפּיוטער וויסנשאַפֿט בוים פריער, לאָזן מיר נעמען דורך טעלינג איר אַז אַ קאָמפּיוטער וויסנשאַפֿט בוים וואקסט אַרונטער. יא, ניט ענלעך ביימער איר זענען צוגעוווינט צו, דער וואָרצל פון אַ קאָמפּיוטער וויסנשאַפֿט בוים איז בייַ דער שפּיץ, און די בלעטער זענען בייַ די דנאָ. יעדער קליין קעסטל איז גערופן אַ נאָדע, און די נאָודז זענען פארבונדן צו יעדער אנדערע דורך עדזשאַז. אַזוי דעם וואָרצל פון דעם בוים איז אַ נאָדע ווערט מיט דעם ווערט 13, וואָס האט 2 קינדער נאָודז מיט די וואַלועס 5 און 34. א סובטרעע איז דער בוים וואָס איז געגרינדעט נאָר דורך קוקן בייַ אַ סאַבסעקשאַן פון די גאנצע בוים. 

פֿאַר בייַשפּיל, די לינקס סובטרעע פון ​​די נאָדע 3 איז דער בוים באשאפן דורך די נאָודז 0, 1, און 2. אַזוי, אויב מיר גיין צוריק צו די פּראָפּערטיעס פון אַ ביינערי זוכן בוים, מיר זען אַז יעדער נאָדע אין דער בוים קאַנפאָרמז צו אַלע 3 פּראָפּערטיעס, ניימלי, די לינקס סובטרעע נאָר כּולל וואַלועס וואָס זענען ווייניקער ווי אָדער גלייַך צו די נאָדע ס ווערט; די רעכט סובטרעע פון ​​אַלע נאָודז נאָר כּולל וואַלועס וואָס זענען גרעסער ווי אָדער גלייַך צו די נאָדע ס ווערט; און ביידע לינקס און רעכט סובטרעעס פון אַלע נאָודז אויך זענען ביינערי זוכן ביימער. כאָטש דעם בוים קוקט אַנדערש, דאָס איז אַ גילטיק ביינערי זוכן בוים פֿאַר דער זעלביקער שטעלן פון נומערן. ווי אַ ענין פון פאַקט, עס זענען פילע מעגלעך וועגן וואָס איר קענען שאַפֿן אַ גילטיק ביינערי זוכן בוים פון די נומערן. נו, לאָזן ס גיין צוריק צו דער ערשטער איינער מיר באשאפן. אַזוי וואָס קענען מיר טאָן מיט די ביימער? נו, מיר קענען זייער פשוט געפֿינען די מינימום און מאַקסימום וואַלועס. די מינימום וואַלועס קענען זייַן געפונען דורך שטענדיק געגאנגען צו די לינקס ביז עס זענען ניט מער נאָודז צו באַזוכן. קאָנווערסעלי, צו געפֿינען די מאַקסימום איינער פשוט נאָר גייט אַראָפּ צו די רעכט אין יעדער צייַט. 

געפונען קיין אנדערע נומער וואָס איז נישט די מינימום אָדער די מאַקסימום איז פּונקט ווי גרינג. זאָגן מיר רע קוקן פֿאַר די נומער 89. מיר פשוט טשעק די ווערט פון יעדער נאָדע און גיין צו די לינקס אָדער רעכט, דיפּענדינג אויף צי די נאָדע ס ווערט איז ווייניקער ווי אָדער גרעסער ווי דער איינער מיר רע קוקן פֿאַר. אַזוי, סטאַרטינג אין דער וואָרצל פון 13, מיר זען אַז 89 איז גרעסער, און אַזוי מיר גיין צו די רעכט. דעמאָלט מיר זען די נאָדע פֿאַר 34, און ווידער מיר גיין צו די רעכט. 89 איז נאָך גרעסער ווי 55, אַזוי מיר פאָרזעצן געגאנגען צו די רעכט. מיר דעמאָלט קומען אַרויף מיט אַ נאָדע מיט די ווערט פון 144 און גיין צו די לינקס. לא און זע, 89 איז רעכט דאָרט. 

אן אנדער זאַך וואָס מיר קענען טאָן איז דרוקן אויס אַלע נומערן דורך פּערפאָרמינג אַ ינאָרדער טראַווערסאַל. אַ ינאָרדער טראַווערסאַל מיטל צו דרוקן אַלץ אויס אין די לינקס סובטרעע נאכגעגאנגען דורך דרוקן די נאָדע זיך און דעמאָלט נאכגעגאנגען דורך דרוקן אַלץ אויס אין די רעכט סובטרעע. פֿאַר בייַשפּיל, לאָזן ס נעמען אונדזער באַליבט ביינערי זוכן בוים און דרוקן אויס די נומערן אין אויסגעשטעלט סדר. מיר אָנהייבן בייַ די וואָרצל פון 13, אָבער איידער דרוק 13 מיר האָבן צו דרוקן אויס אַלץ אין דער לינקס סובטרעע. אַזוי מיר גיין צו 5. מיר נאָך האָבן צו גיין דיפּער אַראָפּ אין דעם בוים ביז מיר געפֿינען די לינקס-רובֿ נאָדע, וואָס איז נול. נאָך דרוקן נול, מיר גיין צוריק אַרויף צו די 1 און דרוקן אַז אויס. דעמאָלט מיר גיין צו די רעכט סובטרעע, וואָס איז 2, און דרוקן אַז אויס. איצט אַז מיר רע געטאן מיט וואָס סובטרעע, מיר קענען גיין צוריק אַרויף צו די 3 און דרוקן עס אויס. ממשיך צוריק אַרויף, מיר דרוקן דעם 5 און דעריבער די 8. איצט אַז מיר האָבן געענדיקט די גאנצע לינקס סובטרעע, מיר קענען דרוקן אויס די 13 און אָנהייבן ארבעטן אויף די רעכט סובטרעע. מיר האָפּקען אַראָפּ צו 34, אָבער איידער דרוק 34 מיר האָבן צו דרוקן אויס זייַן לינקס סובטרעע. אַזוי מיר דרוקן אויס 21; דעמאָלט מיר באַקומען צו דרוקן אויס 34 און באַזוכן זייַן רעכט סובטרעע. זינט 55 האט קיין לינקס סובטרעע, מיר דרוקן עס אויס און פאָרזעצן אויף צו זייַן רעכט סובטרעע. 144 האט אַ לינקס סובטרעע, און אַזוי מיר דרוקן אויס דער 89, נאכגעגאנגען דורך די 144, און לעסאָף די רעכט-רובֿ נאָדע פון ​​233. עס איר האָט עס; אַלע די נומערן זענען געדרוקט אויס אין סדר פון לאָואַסט צו העכסטן. 

אַדינג עפּעס צו דער בוים איז לעפיערעך פּיינלאַס ווי געזונט. אַלע מיר האָבן צו טאָן איז מאַכן זיכער אַז מיר נאָכגיין 3 ביינערי זוכן בוים פּראָפּערטיעס און דאַן אַרייַנלייגן די ווערט ווו עס איז פּלאַץ. זאל ס זאָגן מיר ווילן צו אַרייַנלייגן די ווערט פון 7. זינט 7 איז ווייניקער ווי 13, מיר גיין צו די לינקס. אבער עס ס גרעסער ווי 5, אַזוי מיר דורך צו די רעכט. זינט עס ס ווייניקער ווי 8 און 8 איז אַ בלאַט נאָדע, מיר לייגן 7 צו די לינקס קינד פון 8. וווואַלאַ! מיר ווע צוגעגעבן אַ נומער צו אונדזער ביינערי זוכן בוים. 

אויב מיר קענען לייגן זאכן, מיר בעסער זייַן ביכולת צו אויסמעקן זאכן ווי געזונט. ליידער פֿאַר אונדז, דיליטינג איז אַ קליין ביסל מער קאָמפּליצירט - ניט פיל, אָבער נאָר אַ קליין ביסל. עס זענען 3 פאַרשידענע סינעריאָוז אַז מיר האָבן צו באַטראַכטן ווען דיליטינג יסודות פון ביינערי זוכן ביימער. ערשטער, דער יזיאַסט פאַל איז אַז די עלעמענט איז אַ בלאַט נאָדע. אין דעם פאַל, מיר פשוט אויסמעקן עס און גיין אויף מיט אונדזער געזעלשאַפֿט. זאָגן מיר ווילן צו אויסמעקן דעם 7 אַז מיר נאָר צוגעגעבן. נו, מיר פשוט געפֿינען עס, באַזייַטיקן עס, און אַז ס עס. דער ווייַטער פאַל איז אויב די נאָדע האט בלויז 1 קינד. דאָ מיר קענען אויסמעקן די נאָדע, אָבער מיר ערשטער האָבן צו מאַכן זיכער צו פאַרבינדן די סובטרעע וואָס איז איצט לינקס פּאַרענטלעסס צו דער פאָטער פון די נאָדע מיר נאָר אויסגעמעקט. זאָגן מיר ווילן צו אויסמעקן 3 פון אונדזער בוים. מיר נעמען דעם קינד עלעמענט פון וואָס נאָדע און צוטשעפּען עס צו דער פאָטער פון די נאָדע. אין דעם פאַל, מיר רע איצט אַטאַטשינג די 1 צו די 5. דאס אַרבעט אָן אַ פּראָבלעם ווייַל מיר וויסן, לויט צו די ביינערי זוכן בוים פאַרמאָג, אַז אַלץ אין די לינקס סובטרעע פון ​​3 איז געווען ווייניקער ווי 5. איצט אַז 3 ס סובטרעע איז גענומען זאָרגן פון, מיר קענען אויסמעקן עס. די דריט און לעצט פאַל איז די מערסט קאָמפּלעקס. דאס איז די פאַל ווען די נאָדע מיר ווילן צו אויסמעקן האט 2 קינדער. אין סדר צו טאָן דאָס, מיר ערשטער האָבן צו געפֿינען די נאָדע וואָס האט דער ווייַטער גרעסטער ווערט, ויסבייַטן די צוויי, און דעמאָלט אויסמעקן די נאָדע אין קשיא. נאָטיץ די נאָדע וואָס האט דער ווייַטער גרעסטער ווערט קענען ניט האָבן 2 קינדער זיך זינט זייַן לינקס קינד וואָלט זייַן אַ בעסער קאַנדידאַט פֿאַר די ווייַטער גרעסטן. דעריבער, דיליטינג אַ נאָדע מיט 2 קינדער אַמאַונץ צו סוואַפּינג פון 2 נאָודז, און דעמאָלט דיליטינג איז כאַנדאַלד דורך 1 פון די 2 אַפאָרמענשאַנד כּללים. פֿאַר בייַשפּיל, לאָזן ס זאָגן מיר ווילן צו אויסמעקן דעם וואָרצל נאָדע, 13. דער ערשטער זאַך מיר טאָן איז מיר געפֿינען דעם ווייַטער גרעסטער ווערט אין דער בוים וואָס, אין דעם פאַל, איז 21. מיר דעמאָלט ויסבייַטן די 2 נאָודז, מאכן 13 אַ בלאַט און 21 די הויפט גרופּע נאָדע. איצט מיר קענען פשוט אויסמעקן 13. 

ווי אַלודאַד צו פריער, עס זענען פילע מעגלעך וועגן צו מאַכן אַ גילטיק ביינערי זוכן בוים. ליידער פֿאַר אונדז, עטלעכע זענען ערגער ווי אנדערע. פֿאַר בייַשפּיל, וואָס כאַפּאַנז ווען מיר בויען אַ ביינערי זוכן בוים פון אַ אויסגעשטעלט רשימה פון נומערן? אַלע נומערן זענען נאָר צוגעגעבן צו די רעכט בייַ יעדער שריט. ווען מיר ווילן צו זוכן פֿאַר אַ נומער, מיר האָבן קיין ברירה אָבער נאָר צו קוקן בייַ די רעכט בייַ יעדער שריט. דאס איז נישט בעסער ווי לינעאַר זוכן אין אַלע. כאָטש מיר וועלן נישט דעקן זיי דאָ, עס זענען אנדערע, מער קאָמפּליצירט, דאַטן סטראַקטשערז וואָס מאַכן זיכער אַז דאָס טוט נישט פּאַסירן. אבער, איינער פּשוט זאַך וואָס קענען זייַן געטאן צו ויסמייַדן דעם איז צו נאָר ראַנדאַמלי שאַרן די אַרייַנשרייַב וואַלועס. עס ס העכסט אַנלייקלי אַז דורך טראַפ געלעגנהייַט אַ שאַפאַלד רשימה פון נומערן איז אויסגעשטעלט. אויב דאָס זענען די פאַל, קאַסינאָס וואָלט נישט בלייַבן אין געשעפט פֿאַר לאַנג. 

עס איר האָבן עס. איר איצט וויסן וועגן ביינערי שאַרף און ביינערי זוכן ביימער. איך בין פּאַטריק שמיד, און דאָס איז קס50. [CS50.TV] מען קלאָר ווי דער טאָג וועג וואָלט זייַן צו יבערקוקן די רשימה פון ... [ביפּ] ... די נומער פון זאכן ... יאָ [לאַפס] ... פּאָסטן נאָדע פון ​​234 ... אַוגה. >> יייַ! וואָס איז געווען -