[מוזיק פּלייינג] דאַג לויד: אַלע רעכט. אַזוי ביינערי זוכן איז אַ אַלגערידאַם מיר קענען נוצן צו געפֿינען אַן עלעמענט ין פון אַ מענגע. ניט ענלעך לינעאַר זוכן, עס ריקווייערז אַ ספּעציעל צושטאַנד זיין באגעגנט בעפאָרעהאַנד, אָבער עס ס אַזוי פיל מער עפעקטיוו אויב וואָס צושטאַנד איז, אין פאַקט, מיט. אזוי וואָס ס די געדאַנק דאָ? עס ס טיילן און קאַנגקער. מיר ווילן צו רעדוצירן די גרייס פון די זוכן געגנט דורך האַלב יעדער מאָל אין סדר צו געפֿינען אַ ציל נומער. דעם איז ווו אַז צושטאַנד קומט אין שפּיל, כאָטש. מיר קענען נאָר לעווערידזש די מאַכט פון ילימאַנייטינג העלפט פון די יסודות אָן אַפֿילו קוקן אין זיי אויב די מענגע איז אויסגעשטעלט. אויב עס ס אַ גאַנץ מישן אַרויף, מיר קענען ניט נאָר אויס פון האַנט אַוועקוואַרפן האַלב פון די עלעמענטן, ווייַל מיר טאָן ניט וויסן וואָס מיר ניטאָ דיסקאַרדינג. אבער אויב די מענגע איז אויסגעשטעלט, מיר קענען טאָן אַז, ווייַל מיר וויסן אַז אַלץ צו די לינקס פון ווו מיר איצט זענען מוזן זיין נידעריקער ווי די ווערט מיר ניטאָ איצט בייַ. און אַלץ צו די רעכט פון ווו מיר זענען מוזן זיין גרעסער ווי די ווערט מיר ניטאָ איצט קוקן בייַ. אזוי וואָס ס די פּסעודאָקאָדע טריט פֿאַר ביינערי זוכן? מיר איבערחזרן דעם פּראָצעס ביז די מענגע אָדער, ווי מיר גיינ ווייַטער דורך, סאַב ערייז, קלענערער ברעקלעך פון דער אָריגינעל מענגע, איז פון גרייס 0. רעכענען די מידפּוינט פון די קראַנט סאַב מענגע. אויב די ווערט איר ניטאָ קוקן פֿאַר איז אין אַז עלעמענט פון די מענגע, האַלטן. איר אז עס. אַז ס גרויס. אַנדערש, אויב דער ציל איז ווייניקער ווי וואָס ס אין די מיטל, אַזוי אויב די ווערט מיר רע קוקן פֿאַר איז נידעריקער ווי וואָס מיר זען, איבערחזרן דעם פּראָצעס ווידער, אָבער טוישן די סוף פונט, אָנשטאָט פון ווייל די אָריגינעל גאַנץ פול מענגע, צו זיין פּונקט צו די לינקס פון ווו מיר נאָר געקוקט. מיר געוואוסט אַז די מיטל איז אויך הויך, אָדער דער ציל איז געווען ווייניקער ווי די מיטל, און אַזוי עס מוזן עקסיסטירן, אויב עס יגזיסץ אין אַלע אין די מענגע, ערגעץ צו די לינקס פון די מידפּוינט. און אַזוי מיר וועט שטעלן די מענגע אָרט נאָר צו די לינקס פון די מידפּוינט ווי די נייַ סוף פונט. קאָנווערסעלי, אויב דער ציל איז גרעסער ווי וואָס ס אין די מיטל, מיר טאָן די פּינטלעך זעלביקער פּראָצעס, אָבער אַנשטאָט מיר טוישן די אָנהייב פונט צו זיין נאָר צו די רעכט פון די מידפּוינט מיר נאָר קאַלקיאַלייטאַד. און דעריבער, מיר נעמען די פּראָצעס ווידער. זאל ס וויזשוואַלייז דעם, גוט? אַזוי עס ס אַ פּלאַץ געגאנגען און אויף דאָ, אָבער דאָ ס אַ מענגע פון ​​די 15 עלעמענטן. און מיר רע געגאנגען צו זייַן בעכעסקעם שפּור פון אַ פּלאַץ מער שטאָפּן דעם מאָל. אַזוי אין לינעאַר זוכן, מיר זענען נאָר קאַרינג וועגן אַ ציל. אבער דאָס מאָל מיר ווילן צו זאָרג וועגן ווו זענען מיר סטאַרטינג צו קוקן, ווו זענען מיר סטאָפּפּינג קוקן, און וואָס ס די מידפּוינט פון די קראַנט מענגע. אזוי דאָ מיר גיין מיט ביינערי זוכן. מיר 'רע שיין פיל גוט צו גיין, רעכט? איך בין נאָר געגאנגען צו שטעלן אַראָפּ אונטן דאָ אַ סכום פון ינדאַסיז. דעם איז בייסיקלי פּונקט וואָס עלעמענט פון די מענגע מיר ניטאָ גערעדט וועגן. מיט לינעאַר זוכן, מיר זאָרג, היות ווי מיר דאַרפֿן צו וויסן ווי פילע עלעמענטן מיר ניטאָ יטעראַטינג איבער, אָבער מיר טאָן ניט אַקטשאַוואַלי זאָרגן וואָס עלעמענט מיר רע איצט קוקן בייַ. אין ביינערי זוכן, מיר טאָן. און אַזוי יענע זענען נאָר עס ווי אַ קליין פירער. אַזוי מיר קענען אָנהייבן, רעכט? נו, נישט גאַנץ. געדענקען וואָס איך געזאגט וועגן ביינערי זוכן? מיר קענען ניט טאָן עס אויף אַ ונסאָרטעד מענגע אָדער אַנדערש, מיר זענען נישט געראַנטיינג אַז די זיכער יסודות אָדער וואַלועס זענען נישט ווייל אַקסאַדענאַלי דיסקאַרדיד ווען מיר נאָר באַשליסן צו איגנאָרירן האַלב פון די מענגע. אַזוי שריט איינער מיט ביינערי זוכן איז איר מוזן האָבן אַ אויסגעשטעלט מענגע. און איר קענען נוצן קיין פון די סאָרטינג אַלגערידאַמז מיר ווע גערעדט וועגן צו באַקומען איר צו אַז שטעלע. אַזוי איצט, מיר ניטאָ אין אַ שטעלע ווו מיר קענען דורכפירן ביינערי זוכן. אַזוי לאָזן ס איבערחזרן דעם פּראָצעס שריט דורך שריט און האַלטן שפּור פון וואָס ס געשעעניש ווי מיר גיין. אַזוי דער ערשטער מיר דאַרפֿן צו טאָן איז רעכענען די מידפּוינט פון דעם קראַנט מענגע. גוט, מיר וועט זאָגן מיר ניטאָ, ערשטער פון אַלע, קוקן פֿאַר די ווערט 19. מיר 'רע טריינג צו געפֿינען די נומער 19. דער ערשטער עלעמענט פון דעם מענגע איז ליגן אין אינדעקס נול, און די לעצטע עלעמענט פון דעם מענגע איז ליגן אין אינדעקס 14. און אַזוי מיר וועט רופן די אָנהייב און סוף. אַזוי מיר רעכענען די מידפּוינט דורך אַדינג 0 פּלוס 14 צעטיילט דורך 2; שיין סטראַיגהטפאָרוואַרד מידפּוינט. און מיר קענען זאָגן אַז די מידפּוינט איז איצט 7. אַזוי איז 15 וואָס מיר ניטאָ קוקן פֿאַר? ניין, עס ס ניט. מיר 'רע איר זוכט פֿאַר 19. אבער מיר וויסן אַז 19 איז גרעסער ווי וואָס מיר געפֿונען אין דער מיטן. אַזוי וואָס מיר קענען טאָן איז טוישן די אָנהייב פונט צו זיין פּונקט צו די רעכט פון די מידפּוינט, און איבערחזרן די פּראָצעס ווידער. און ווען מיר טאָן אַז, מיר איצט זאָגן די נייַ אָנהייבן פונט איז מענגע אָרט 8. וואָס מיר ווע Effectively געטאן איז איגנאָרירט אַלץ צו די לינקס פון 15. מיר ווע ילימאַנייטאַד העלפט פון די פּראָבלעם, און איצט, אָנשטאָט ווייל צו זוכן איבער 15 עלעמענטן אין אונדזער מענגע, מיר נאָר האָבן צו זוכן איבער 7. אַזוי 8 איז די נייע אָנהייב פונט. 14 איז נאָך דעם סוף פונט. און איצט, מיר גיין איבער דעם ווידער. מיר רעכענען די נייַ מידפּוינט. 8 פּלוס 14 איז 22, צעטיילט דורך 2 איז 11. איז דעם וואָס מיר ניטאָ קוקן פֿאַר? ניין, עס ס ניט. מיר ניטאָ קוקן פֿאַר אַ ווערט אַז ס ווייניקער ווי וואָס מיר נאָר געפֿונען. אַזוי מיר רע געגאנגען צו איבערחזרן דער פּראָצעס ווידער. מיר רע געגאנגען צו טוישן די סוף פונט צו זייַן נאָר צו די לינקס פון די מידפּוינט. אזוי די נייַ סוף פונט ווערט 10. און איצט, אַז ס די בלויז טייל פון די מענגע מיר האָבן צו סאָרט דורך. אַזוי מיר האָבן איצט ילימאַנייטאַד 12 פון די 15 עלעמענטן. מיר וויסן אַז אויב 19 יגזיסץ אין די מענגע, עס מוזן עקסיסטירן ערגעץ צווישן עלעמענט נומער 8 און עלעמענט נומער 10. אַזוי מיר רעכענען די נייַ מידפּוינט ווידער. 8 פּלוס 10 איז 18, צעטיילט דורך 2 איז 9. און אין דעם פאַל, קוק, די ציל איז ביי דער מיטן. We found פּונקט וואָס מיר ניטאָ קוקן פֿאַר. מיר קענען האַלטן. מיר הצלחה געענדיקט אַ ביינערי זוכן. אַלע רעכט. אַזוי מיר וויסן דעם אַלגערידאַם אַרבעט אויב דער ציל איז ערגעץ ין פון די מענגע. טוט דעם אַלגערידאַם אַרבעט אויב דער ציל איז נישט אין די מענגע? נו, לאָזן ס אָנהייבן עס ווידער, און דאָס מאָל, זאל ס קוק פֿאַר די עלעמענט 16, וואָס וויזשוואַלי מיר קענען זען טוט נישט עקסיסטירן ערגעץ אין די מענגע. דער אָנהייב פונט איז ווידער 0. דער סוף פונט איז ווידער 14. יענע זענען די ינדאַסיז פון דער ערשטער און לעצטע יסודות פון די גאַנץ מענגע. און מיר וועט גיין דורך די פּראָצעס מיר נאָר געגאנגען דורך ווידער, טריינג צו געפֿינען 16, אַפֿילו כאָטש וויזשוואַלי, מיר קענען שוין זאָגן אַז עס ס ניט געגאנגען צו זיין דאָרט. מיר נאָר ווילן צו מאַכן זיכער דעם אַלגערידאַם וועט, אין פאַקט, נאָך אַרבעט אין עטלעכע וועג און ניט נאָר לאָזן אונדז סטאַק אין אַ אַנלימאַטאַד שלייף. אזוי וואָס ס די שריט ערשטער? רעכענען די מידפּוינט פון די קראַנט מענגע. וואָס ס די מידפּוינט פון די קראַנט מענגע? נו, עס ס 7, רעכט? 14 פּלוס 0 צעטיילט דורך 2 איז 7. איז 15 וואָס מיר ניטאָ קוקן פֿאַר? נומ עס ס שיין נאָענט, אָבער מיר 'רע איר זוכט פֿאַר אַ ווערט אַ ביסל ביגער ווי אַז. אַזוי מיר וויסן אַז עס ס געגאנגען צו זיין ינ ערגעצ ניט צו די לינקס פון 15. דער ציל איז גרעסער ווי וואָס ס אין די מידפּוינט. און אַזוי מיר שטעלן די נייַ אָנהייב פונט צו זיין פּונקט צו די רעכט פון די מיטל. די מידפּוינט איז איצט 7, אַזוי לאָזן ס זאָגן די נייע אָנהייב פונט איז 8. און וואָס מיר ווע Effectively געטאן ווידער איז איגנאָרירט די גאנצע לינקס האַלב פון די מענגע. איצט, מיר איבערחזרן די פּראָצעס איינער מער צייַט. רעכענען די נייַ מידפּוינט. 8 פּלוס 14 איז 22, צעטיילט דורך 2 איז 11. איז 23 וואָס מיר ניטאָ קוקן פֿאַר? צום באַדויערן, ניט. מיר ניטאָ קוקן פֿאַר אַ ווערט אַז איז ווייניקער ווי 23. און אַזוי אין דעם פאַל, מיר רע געגאנגען צו טוישן די סוף פונט צו זיין פּונקט צו די לינקס פון די קראַנט מידפּוינט. די איצטיקע מידפּוינט איז 11, און אַזוי מיר וועט שטעלן די נייַ סוף פונט פֿאַר די ווייַטער צייַט מיר גיין דורך דעם פּראָצעס צו 10. ווידער, מיר גיין דורך די פּראָצעס ווידער. רעכענען די מידפּוינט. 8 פּלוס 10 צעטיילט דורך 2 איז 9. איז 19 וואָס מיר ניטאָ קוקן פֿאַר? צום באַדויערן, ניט. מיר ניטאָ נאָך קוקן פֿאַר אַ נומער ווייניקער ווי אַז. אזוי מיר וועט טוישן דעם סוף פונט דאָס מאָל צו זיין פּונקט צו די לינקס פון די מידפּוינט. די מידפּוינט איז איצט 9, אַזוי דעם סוף פונט וועט זיין 8. און איצט, מיר ניטאָ נאָר קוקן אין אַ איין עלעמענט מענגע. וואָס ס די מידפּוינט פון דעם מענגע? נו, עס סטאַרץ בייַ 8, עס ענדס אין 8, די מידפּוינט איז 8. איז אַז וואָס מיר ניטאָ קוקן פֿאַר? זענען מיר קוקן פֿאַר 17? ניין, מיר 'רע איר זוכט פֿאַר 16. אַזוי אויב עס יגזיסץ אין די מענגע, עס מוזן עקסיסטירן ערגעץ צו די לינקס פון ווו מיר איצט זענען. אזוי וואָס זענען מיר געגאנגען צו טאָן? גוט, מיר וועט שטעלן די סוף פונט צו זיין פּונקט צו די לינקס פון די קראַנט מידפּוינט. אזוי מיר וועט טוישן דעם סוף פונט צו 7. צי איר זען וואָס נאָר געשען דאָ, כאָטש? קוק אַרויף דאָ איצט. אָנהייב איז איצט גרעסער ווי סוף. Effectively, די צוויי ענדס פון אונדזער מענגע האָבן קראָסט, און דער אָנהייב פונט איז איצט נאָך דעם סוף פונט. נו, וואָס טוט ניט מאַכן קיין זינען, רעכט? אַזוי איצט, וואָס מיר קענען זאָגן איז מיר האָבן אַ סאַב מענגע פון ​​גרייס 0. און אַמאָל מיר ניטאָ גאַטאַן צו דעם פונט, מיר קענען איצט גאַראַנטירן אַז עלעמענט 16 טוט נישט עקסיסטירן אין די מענגע, ווייַל די אָנהייב פונט און סוף פונט האָבן קראָסט. און אַזוי עס ס נישט דאָרט. איצט, באַמערקן אַז דאָס איז אַ ביסל אַנדערש ווי די אָנהייב פונט און סוף פונט ווייל די זעלבע. אויב מיר האט שוין קוקן פֿאַר 17, עס וואָלט האָבן שוין אין די מענגע, און דער אָנהייב פונט און סוף פונט פון אַז לעצט יטעראַטיאָן איידער די פּוינץ קראָסט, מיר וואָלט האָבן געפֿונען 17 עס. עס ס נאָר ווען זיי קרייַז אַז מיר קענען גאַראַנטירן אַז די עלעמענט טוט ניט עקסיסטירן אין די מענגע. אַזוי לאָזן ס נעמען אַ פּלאַץ ווייניקערע טריט ווי לינעאַר זוכן. אין די ערגסטע פאַל סצענאַר, מיר האט צו שפּאַלטן אַרויף אַ רשימה פון N עלעמענטן ריפּיטידלי אין האַלב צו געפֿינען די ציל, אָדער ווייַל דער ציל עלעמענט וועט זיין ערגעץ אין די לעצטע אָפּטייל, אָדער עס טוט נישט עקסיסטירן אין אַלע. אַזוי אין די ערגסט פאַל, מיר האָבן צו שפּאַלטן אַרויף די אַררייַ-- טאָן איר וויסן? קלאָץ פון N מאל; מיר האָבן צו שנייַדן די פּראָבלעם אין האַלב אַ זיכער נומער פון מאל. אַז נומער פון מאל איז קלאָץ ען. וואָס ס דער בעסטער פאַל סצענאַר? נו, דער ערשטער מאָל מיר רעכענען די מידפּוינט, מיר געפֿינען וואָס מיר ניטאָ קוקן פֿאַר. אין אַלע די פרייַערדיק יגזאַמפּאַלז אויף ביינערי זוכן מיר ווע נאָר ניטאָ איבער, אויב מיר האבן שוין קוקן פֿאַר דער עלעמענט 15, מיר וואָלט האָבן געפֿונען אַז מיד. וואס איז געווען בייַ די זייער אָנהייב. וואס איז געווען די מידפּוינט פון דער ערשטער פּרווון בייַ אַ שפּאַלטן פון אַ אָפּטייל אין ביינערי זוכן. און אַזוי אין די ערגסט פאַל, ביינערי זוכן ראַנז אין קלאָץ N, וואָס איז סאַבסטאַנשאַלי בעסער ווי לינעאַר זוכן, אין די ערגסטע פאַל. אין דער בעסטער פאַל, ביינערי זוכן ראַנז אין תוו פון 1. אַזוי ביינערי זוכן איז אַ פּלאַץ בעסער ווי לינעאַר זוכן, אָבער איר האָבן צו האַנדלען מיט די פּראָצעס פון סאָרטינג אייער מענגע ערשטער איידער איר קענען לעווערידזש די מאַכט פון ביינערי זוכן. איך בין דאַג לויד. דאס איז קס 50.