揚聲器1：嗨大家好！ 歡迎回到一節。 很高興見到你們這麼多人都在這裡， 大家誰的在線觀看。 所以，像往常一樣，歡迎回來。 我希望大家都度過了一個可愛 週末，得到充分的休息，放鬆。 這是美麗的昨天。 所以，我希望你喜歡戶外活動。 

因此，首先一對夫婦公告。 分級。 所以，你最應該得到的 從我的電子郵件你刮的Pset， 以及分級的Pset中1。 所以，只是一對夫婦的事情。 請務必使用check50在style50。 這些都意味著是 資源為你們， 確保你得到 盡可能多的點，你可以 沒有不必要的失去他們。 所以像風格 是非常重要的。 我們要起飛了。 你們有些人可能已經 注意到，從你的pset中。 和check50僅僅是一個 非常簡單的方法，以確保 那我們實際上回歸了什麼 需要被返回給用戶， 而這一切的正常工作。 

在第二個音符時，請確保您的 上傳東西到正確的文件夾中。 它使我的生活只是一個 更困難一點 如果你上傳的Pset 2成1的Pset 因為當我下載的東西， 他們不能正確下載。 我知道這是一個有點靠不住 在一個系統中使用的獲得， 但只是超 小心，如果只是對我來說， 所以，當你得到的郵件 在像上午02點我就是分級。 如果沒有引起我要看看 各地為您的Pset。 涼爽。 

我知道這是早期的，但我 完全得到起飛後衛 通過一篇短文這是本週五到期，該 我的教授只是喜歡，哦耶。 請記住，你有一個 文章將於週五公佈。 所以，我知道沒有人喜歡 想想期中考試， 但你的第一次測驗是10月15日， 其中10月份這個星期開始。 因此，它可能是遲早 比你預期的是一切。 讓你不扔猝不及防的時候 我提到下週一節哦， 您的測驗接下來的一周，我想 我願意給你一點點 的抬起頭來了。 

所以，你的問題集，排名第三。 人如何閱讀 規範的好奇心了呢？ 行。 我們有一對夫婦。 那種從上向下 本週不過沒關係。 我知道這是美麗的。 因此爆發。 一定時間後就會完成 今天看了你的天賦，至少 嘗試像下載 發行代碼並運行 像第一初始 他們問你要的東西。 因為我們使用 分配代碼和一個圖書館 我們只是一直在using-- --IT只是 第二次我們已經做到了這一點的Pset， 瘋狂的事情都可能發生 與您的設備， 你想找到 從現在與以後。 

因為如果是週四晚上或它的 週三晚上，由於某種原因 您的設備少了點 要與庫運行 或用分配 代碼，這意味著 你甚至不能開始做編碼。 因為你不能檢查 來看看它的工作原理。 你不會是能夠 看它是否編譯。 你想在早期照顧那些 本週，當你仍然可以給我發電子郵件 或其他轉錄因子中的一個， 我們可以得到這些固定的。 因為這些都是問題 這會阻止你 做任何實際進展。 它不象1的bug，那 有種你就跳過。 如果您遇到問題，您 設備或分發代碼， 你真的想要得到所採取的 呵護宜早不宜遲。 所以，即使你不會真正 開始編碼，下載發行 碼，讀取規格，確保 一切都在那裡工作。 行？ 如果你可以做到這一點，我 答應你的生活會更容易。 所以你很可能會 要做到這一點，現在好嗎？ 行。 那麼，有什麼問題嗎？ 任何邏輯的東西呢？ 大家的好？ 行。 

免責聲明對於那些 你在房間裡上網。 我將要嘗試切換 PowerPoint中的裝置之間 因為我們要 是做一些編碼 今天流行的匿名需求 調查建議我送出去的最後一周。 所以，我們會做一些編碼。 所以，如果你們也想 火了你的設備， 你應該已經得到了一封電子郵件， 從我來說，有一個示例文件。 請隨時做。 

所以，我們要談 GDB，這是一個調試程序。 這將幫助你 種揣摩出 事情會出錯的代碼。 這真的只是一個方法可以讓你一步 通過你的代碼，它的發生， 並能夠打印出變量 或者看看有什麼實際發生 引擎蓋下的詩句程序 剛運行時，它就像斷層， 和你一樣，不知道 這裡剛剛發生了什麼。 我不知道它沒有在哪一行。 我不知道哪裡出了問題。 因此，GDB會幫助你的。 另外，如果你決定 繼續沒錯，走61， 它真的，真的是你 最好的朋友，因為我可以告訴你 因為我要通過這個類。 

我們要看看二進制 搜索，這如果你們還記得 偉大的電話簿例子 眼鏡從類。 我們將實現這一點， 通過多一點點走， 然後我們要通過四個 不同種類的，這是泡沫， 選擇，插入和合併。 涼爽。 所以，GDB正如我所說，是一個調試器。 而這些都是一種大的 的東西，大的功能或命令 您在使用GDB，我會走 你通過它在第二演示。 

所以，這不僅是 要留抽象。 我會試著讓它混凝土 盡可能為你們。 因此，突破。 它會要么是突破 象，一些數量，這 代表你的程序行， 或者，你可以命名的功能。 所以，如果你說分手主力， 它會停在主， 並且讓你通過該功能走路。 

同樣，如果你​​有一些外部 功能類似於交換或多維數據集， 我們看最後一周。 如果你說破其中的一個， 只要你的程序打了， 就等你來 告訴它要做什麼。 之前，它只會執行，所以你 可以在函數內部實際步驟 看看是怎麼回事。 所以，接下來，就跳過了 下一行，越過功能。 步驟。 這些都是有點抽象。 所以，我只是通過他們的運行， 但你會看到他們在第二次使用。 

步入函數。 因此，正如我所說， 像交換，它會 讓你真正的，如果你 就像身體裡面的加強， 你可以亂用這些變量，打印 它們是什麼，看看發生了什麼事情。 名單將字面上只是打印 從周圍的代碼。 所以，如果你種忘了 你在哪裡在你的程序中， 或者你想知道 這是怎麼回事周圍， 這將只打印出一個段 都喜歡它周圍的五六行。 所以，你可以得到導向 關於你在哪裡。 

打印一些變量。 所以，如果你有這樣的關鍵 在愷撒，那我們來看看。 你可以說在任何時候打印鍵。 它會告訴你的價值就是如此 這，也許某個地方一路走來， 你重寫你的關鍵。 實際上，你可以告訴大家，因為 你其實可以觀察到的價值。 

在當地人，只是版畫 你的局部變量。 所以，任何時候，你是在一個循環中， 而你只是想看看像哦。 什麼是我的嗎？ 這是什麼鍵值 我在這裡初始化？ 這是在這一點上的信息？ 它只是將打印所有 那些的，這樣就 不必單獨地 說，打印一打印信息。 打印鍵。 然後顯示。 這是什麼做的是為你 單步執行程序， 它會只是確保它的 顯示一定的變數 在每一點上。 所以，你also-- --IT是 一種快捷方式，其中的 你沒有堅持下去似的，呵呵。 打印鍵或打印一，這只是 將自動為您代勞。 

因此，在這一點，我們要去 怎麼看這樣下去。 我要去嘗試和開關 在我的設備。 看看我能做到這一點。 全部。 我們只是要鏡像。 沒有什麼瘋狂 我的筆記本電腦反正。 行。 這需要這個。 它是如此的渺小。 讓我們來看看，如果我們能做到這一點。 

行。 愛麗絲顯然是掙扎 這裡只是一點點， 但我們會讓它在你幾分鐘。 行。 我們只是要增加這一點。 行。 種可大家看到了嗎？ 也許一點點？ 我知道這是小了點。 你不能完全弄清楚 如何使這個更大。 如果有人知道。 有誰知道如何使它更大？ 行。 我們將推出它。 不要緊，反正，因為它只是 這是代碼，你們應該 有。 

什麼是更重要的 是這裡的端子。 而我們在這裡為什麼會這麼少呢？ 設置。 呵呵。 真正的艾克。 這個怎麼樣？ 離開那裡。 是為大家好？ 行，。 涼爽。 

你知道，當你在CS 一流的技術困難 是善良的the--一部分 所以，讓我們澄清這一點。 行。 所以，這裡的部分， 我們不得不在這裡。 凱撒是一個可執行文件。 所以，我做到了。 所以，有一點要實現與GDB是 它僅適用於可執行文件。 所以，你不能在dotsy運行它。 你要真正使 確保你的代碼編譯， 並且，它可以實際運行。 

因此，請相信，如果它不 編譯，得到它的編譯， 這樣就可以通過它種上運行。 因此，要啟動GDB，你所要做的， 凱萊型GDB，然後就在 文件，你想要的。 我總是拼錯撒。 但是你要確保 因為它是一個可執行文件， TI的圓點閃爍，使 意味著你要 運行CSI你要執行 此文件或者與調試。 行。 所以，你這樣做，你會得到 這種亂碼。 這只是所有關於調試的東西。 你不會真的要 擔心現在。 正如你看到的，我們有這個 開括號，國內生產總值，接近括號， 而那種只是看起來像 我們的命令行，對不對？ 

所以，我們要do--  - 因此，第一件事 就是我們要選 一個地方打破它。 所以，有一個錯誤 在這個程序凱撒 我介紹一下，這 我們要了解一下。 它是做什麼是需要輸入 Barfoo全部大寫，並由於某種原因 它只是離開它不會改變A. 孤軍奮戰，是一切正確， 但第二個字母 A保持不變。 所以，我們要嘗試 弄清楚這是為什麼。 所以，第一件事情，你通常 想要每次啟動GDB上做 是從哪裡打破它。 

因此，凱撒是一個很短的程序。 我們只是有一個功能，對不對？ 什麼是我們的凱撒功能？ 這裡只有一個功能，主要對不對？ 主要是功能 您的所有程序。 如果沒有主，我可能會 是有點擔心，現在， 但我希望你們都在那裡有主。 所以，我們可以做的是，我們可以 剛剛突破主，就這樣。 因此，它說，OK。 我們設置了斷點，一個人也沒有。 

所以，現在要記住的是凱撒 需要一個命令行參數的權利 我們還沒有做到這一點還沒有任何地方。 所以，你要做的就是當 你居然去跑 該程序，你是任何程序 在GDB運行需要的命令行 參數，你要輸入 當你第​​一次啟動運行它。 所以，在這種情況下，我們做 與三支一鍵運行。 它會真正開始。 

所以，如果你看到這裡，我們有 如果RC不等於2。 所以，如果你們都 我送出了該文件 你會看到，就像 第一行我們的主要功能，對不對？ 它的檢查，看看是否有 正確數目的參數。 所以，如果你想知道 如果RC是正確的， 你可以做一些事情，就像打印RC。 RC為2，這是 我們所預期的，對不對？ 

因此，我們可以去下， 並繼續通過。 因此，我們有一些關鍵的有。 我們可以打印出我們的關鍵 以確保是正確的。 有意思的。 並不完全符合我們的預期。 所以，有一點認識 用GDB也，是 它不是，直到你竟然打 接下來，你剛才看到的行 實際執行。 所以，在這種情況下關鍵 尚未分配愛好。 所以，關鍵是一些垃圾的價值 您在底部有看到。 負$ 120-- --IT堅持一個十億 和一些奇怪的事情吧？ 這不是我們所期望的關鍵。 但是，如果我們點擊Next，然後我們 嘗試打印鍵，它是三種。 

大家看到了嗎？ 所以，如果你得到的東西 那你喜歡，請等待。 這是完全 錯了，我不知道 怎麼會發生這種事，因為我想要的 做的是分配一個編號，變量 試著打接下來，嘗試印刷 一遍，看看是否可行。 因為它只會執行和 之後，你實際上分配的東西 點擊Next。 道理大家？ 嗯？ 

揚聲器2：當你隨意 數字是什麼意思呢？ 

揚聲器1：這只是隨機的。 這只是垃圾。 這只是一些你 電腦會隨機分配。 涼爽。 所以，現在我們可以通過移動，等等 現在我們有這個純文本的GetString。 所以，讓我介紹什麼 會發生什麼，當我們點擊Next這裡。 種了GDB消失了，對不對？ 這是因為GetString的 現在執行的，對不對？ 所以，當我們看到純文本等於 GetString的，開放的括號和括號， 和我們打接下來，有 實際執行了。 因此，它在等待 我們輸入一些東西。 

所以，我們要輸入我們的食物， 就是它的失敗，因為我告訴過你 那只是說，這是 完成執行，該封閉 支架是指它的 退出了該循環。 因此，我們可以接著打，而現在，因為我 確保你所有的從凱撒熟悉， 這，這是什麼行會的事情。 這對INT I等於0，N等於 strlen的，純文本，然後 我是小於n，I，加，加。 什麼是這個循環怎麼辦呢？ 打開你的郵件。 涼爽。 那麼，讓我們開始這樣做。 

因此，應此條件 匹配，我們的第一個？ 如果它是一個B，這是純文本格式一，我們 可以了解我們當地人的信息。 所以，我是零​​，而如果6，其 我們希望，我們的重點是三。 所有這一切是有意義的，對嗎？ 這些數字都 正是他們應該的。 因此，哼？ 揚聲器3：我有 隨機數我的。 揚聲器1：嗯，我們可以check--  - 我們 可以聊，在第二。 但是，你應該得到這個。 所以，如果我們有一個資本 B我們的第一個， 這種情況下應該抓住它，對不對？ 所以，如果我們打接下來，我們看到 這如果實際執行。 因為如果你是以下 沿著你的代碼， 這條線在這裡，在純文本我 替換為算術， 僅當如果執行 條件是正確的嗎？ 

GDB只是要告訴你 這是實際執行的東西。 所以，如果沒有達到這個如果條件下，它的 只是要跳到下一行。 行？ 因此，我們有。 這架意味著它 現在關閉了該循環。 因此，它會重新開始。 就這樣。 因此，我們可以得到的信息 關於我們當地人在這裡， 我們看到，我們的第一個 信改變了，對不對？ 它現在是E，因為它應該是。 因此，我們可以繼續。 

我們有這個檢查。 而這種檢查應該工作了吧？ 這是A.應該改變 三個字母前進。 但是，如果你注意到，我們 得到不同的東西。 所以在這種情況下在這裡，它抓 它，因此這條線執行， 它修改了我們的B. 但是，在這裡這種情況下， 我們認為它只是跳過它， 並到[？ L SIFF。 ？] 因此，一些對那裡發生。 什麼是告訴你的是， 我們知道，它應該在這裡趕， 但事實並非如此。 任何人都可以看到我們的 問題是在該行？ 這是一個非常微小的事情。 你也可以看看你的代碼。 它也line--忘了這是什麼線 在那裡 - 但它在[聽不清]。 是嗎？ 

揚聲器4：這是在比大 頁面，如果你在書中讀到它。 揚聲器1：沒錯。 所以，調試分不清楚 你說，但是調試器 可以讓你下到一條線 你知道不正常。 有時候，特別是當 後來在學期中，當 你處理了一百，一 百幾行代碼，你 不知道它的失敗， 這是一個偉大的方式來做到這一點。 所以，我們發現我們的錯誤。 您可以修復它在你的文件， 然後，你可以再次運行它， 一切都將正常工作。 而最重要的事情是 這似乎是，OK。 是啊。 涼爽。 你知道你在尋找什麼。 所以，你知道該怎麼做。 

GDB可能是因為你超級有幫助 可以打印出所有這些東西，你 不會。 它比的printf有用得多。 你們有多少人使用 如printf語句 找出其中的錯誤是，對不對？ 所以，這一點，你不 必須保持回去， 和喜歡的評論 printf的，或者註釋掉， 並找出哪些 你應該打印。 這實際上只是讓你 步，打印出來的東西 當你正在經歷，所以，你可以 觀察他們在現實時間的變化， 因為你的程序正在運行。 

它確實需要一點點 對習慣一下。 我會強烈建議正中下懷 的是一個有點沮喪吧 對於現在。 如果你在花一個小時 下週學習如何使用GDB， 你能救自己 如此多的時間以後。 和字面上。告訴我們 這人年年有， 我記得，當我把 類，我很喜歡，我會沒事的。 號 PSET 6來了，我是 喜歡，我要學習 如何使用GDB，因為我不 知道是怎麼回事。 

如果你花時間，所以， 使用它的小程序 那你會是 工作，喜歡工作 通過類似 Visionare，是這樣的。 或者，如果你想要額外的練習，我敢肯定， 我可以用bug的程序上來， 為您調試，如果你願意的話​​。 

但如果你只是需要一些時間來獲得 習慣了，只是玩它， 它真的會滿足你的需要。 而且它是真正的一個 那些東西，你只是 必須嘗試，並得到你的手臟 用，在你真正了解它。 我真的只聽懂了一次 我調試的東西吧， 和它的更漂亮有一個想法 如何調試宜早不宜遲。 行。 涼爽。 我知道這有點像 速成班GDB， 我一定會努力的讓 這些看起來更大下一次。 涼爽。 

所以，如果我們回到我們的PowerPoint。 這是去上班？ AWH。 是。 行。 所以，如果你需要任何 這些再次，還有的列表。 所以二進制搜索，人人 記得大衛的偉大奇觀 撕成兩半電話簿。 我真的不明白了 電話簿了， 因為喜歡你在哪裡 獲取電話簿可好？ 我真的不知道。 二進制搜索。 有誰還記得 如何二進制搜索作品？ 人呢？ 是嗎？ 揚聲器5：你知道什麼時候 你看看是哪一半 這將是在，在此基礎上， 和擺脫的另一半。 

揚聲器1沒錯。 因此，二進制搜索，它是一種A--  - 我們喜歡叫它分而治之。 所以，你要做的是 你將看到在中間， 你會看它是否符合 您要查找的內容。 如果沒有，那麼你嘗試 搞清楚，它是將要離開 一半或右半部。 所以，這可能是如果你正在尋找 在東西是按字母順序排列， 你看，哦。 難道佳佳來到先於M？ 是。 所以，我們要 看看上半場。 

或者它可能是像數字。 什麼，你可以 比較，就可以進行排序。 您可以使用二進制搜索。 因此，任何人都記住了這個 圖表或這是什麼？ 這是漸近複雜性。 因此，此圖只 介紹了多長時間 你需要解決一個問題， 你增加多少東西 您正在使用。 

因此，我們有N個，其是直鏈的時間。 如果N超過2，略 好，還是成長超快。 然後我們登錄，這是 我們認為二分查找。 如果我們注意到，作為您的問題 變多，大得多， 它把你的時間來解決它 並沒有真正增加那麼多。 這就像媲美 在這裡開始。 你就像，OK。 任何事情在這裡並沒有真正 無論哪一種我們使用， 但你得到了一百萬，一十億。 你想找到some-- --you're 試圖找到大海撈針。 

我想你想這個問題。 你想這種複雜性，不 線性的，因為所有你 知道你會通過搜索來 每個單獨的針，乾草的事情， 試圖尋找你的針。 而這還不是在我看來，太好玩了。 我喜歡快。 我喜歡有效率。 而作為勤奮的學生，你 傢伙，你知道的更聰明地工作， 而不是更辛苦類型的事情，你怎麼 可以彌補這些算法。 

所以，我們要走路 僅僅通過一個簡單的例子。 我想你們應該有 在二進制搜索手， 但在任何情況下，一點點 模糊，要加強它， 我們打算才行 通過這裡的例子。 所以，我們要尋找的，如果 該數組包含七個。 

所以，我們首先要做的就是 看在中間，對不對？ 而且你要被編碼 在短短的二二分查找。 因此，這將很有趣。 因此，我們期待在 中間的小數組3。 3是否等於7？ 沒有。 這是6。 那麼，是不是小於 或大於7？ 少於。 是。 幹得漂亮傢伙。 我覺得我我應該 有糖果，因為我 想要把它伸到碼。 這就是我將在下週的事。 這將讓你們鋒利。 

所以，我們扔掉了 上半年，對不對？ 這是小於。 我們知道，一切 在該左側 將是小於什麼 我們實際上是在尋找。 所以，沒有必要 注意它。 忘掉它。 所以，現在我們看一下我們的右手邊， 我們期待在中間那邊， 現在它是9。 因此，9 is-- --Everyone？ 比我們大 找了吧？ 因此，我們要扔掉 客場的一切權利。 這樣。 現在，我們只剩下一個。 所以我們檢查，是這個東西 我們正在尋找什麼？它是。 我們發現我們想要的。 所以，我們就大功告成了。 雙線性搜索。 

如果你注意到，我們 有七個輸入存在。 只花了我們喜歡的三倍， 但如果你正在做的像一個十億， 你們知道要走多少步會 走，如果我們有四十億的事情呢？ 任何猜測？ 這是32。 32步找到的東西 在四十億 因為兩個大國的元素數組。 所以，二是32個，是四十億。 

所以很瘋狂怎麼你還在內 像一個相當小的數目的步驟 找東西 four十億元素。 所以，關於這一點，我們 將這個代碼 所以你們其實可以 樣的了解其工作原理。 好吧，讓你們可以代碼。 我將讓你們 聊了一點點。 了解你周圍的人，這是 從最後一節什麼人想要的。 

所以，了解你周圍的人。 聊了一點點。 和所有我想從你 你們現在只是 嘗試創建偽代碼的輪廓。 行？ 哇。 所有我想從你們這些傢伙是你 只是要填補這一情況時。 所以我已經設置了這些上 界和下界哪 代表開始 我們的陣列和末端。 而你要真正 遍歷並找出 我們正在做的這個while循環中。 

所以，如果你自己看著辦out--我 暗示那裡 - 是什麼情況 我們有嗎？ 所以，如果你想弄清楚的 的情況下，我們將這些偽 然後我們就可以真的實現它們。 而這將是我 想想，希望它會 比預期的更容易一些。 因為它沒有那麼多的代碼， 其實，這是真的很酷。 

嗯？ 

學生：[聽不清]？ 指導老師：是的。 有一件事 發現在中間。 

學生：所以我們可以使用它。 行。 

講師：完美。 所以這是我們需要做的第一件事。 所以，找到中間。 太好了。 所以，你有一個想法，我們怎麼可能 實際上找到的代碼中間？ 

學生：是啊。 ñ超過2？ 講師：因此n超過2。 所以，有一點要記住的是， 你的上界和下界改變。 我們不斷收縮的部分 數組的，我們正在尋找。 因此n超過2只會工作 對於第一件事，我們做的。 因此服用上下兼顧， 怎麼可能，我們得到了中量元素？ 因為我們想要中間 之間的上，下，右？ 嗯？ 

學生：[聽不清]。 

講師：所以我們有一些中間。 而這將是上加下超過2。 真棒。 在那裡，我們走了。 一號線下來。 你們是在用自己的方式。 所以，現在，我們有我們 中間，有什麼事我們想幹什麼？ 只是一般。 您不必編寫它。 是。 學生：[聽不清]？ 講師：所以這是加，因為你 發現兩者之間的平均 對他們。 所以，如果你認為它們是一種 在從側面增加， 想想看，當你接近 中間，你想這樣的。 所以，如果你是對的兩邊 中間，我們有像5和7。 當你把它們加起來，你 得到12，你除以2，就是6。 

有時候很難 解釋為什麼這樣的作品， 但如果你的工作，通過 一個例子有時候， 它會幫你計算出，如果 它應該是正或負。 是。 

學生：[聽不清] 恰好在中間 如果他們的情況 還有很多小的數字 而像一個大的數量？ 

講師：所以你需要 是陣列的中間。 所以，如果你有一堆小數字 再一個真正大量 在末端，也沒關係。 所有的事情是， 他們排序，你只要 想看看中間 數組是因為你還 一半切片您的問題。 涼爽。 所以，現在，我們有 中間，我們接下來做什麼？ 

學生：比較。 講師：當比較。 所以比較中間value_wanted。 涼爽。 所以你看在這裡，我們有 我們要在這裡這個值。 請記住，這是一個數組。 所以中間是指索引。 所以，我們要做的中間值。 如果你想不要忘記 比較，雙等號​​。 你做單等於你 只是要重新分配它， 然後，當然，它們也 會是你想要的值。 所以，不要那樣做。 

所以，我們要如果看 在中間的值 等於我們想要的值。 不要忘了你的牙套。 Dropbox的應該消失。 那麼，我們在這種情況下怎麼辦？ 如果它是什麼，我們要回去呢？ 我們想說的。 

學生：打印關閉。 

講師：嗯，我們 不想打印出來。 因此，這是這裡的布爾值，因此我們 要返回true或false。 我們要說的，就是這個號碼 一個[？ RRA？ ？]因此，如果它是， 我們只是回到它真實的。 如果我能拼寫正確。 

學生：你為什麼不回零？ 講師：所以，你可以 返回零，如果你想要的。 但在這種情況下，因為 我們的函數返回一個布爾值， 我們需要返回true或false。 學生：當你 話說布爾表達式， 你可以將其設置為假？ 就像如果我想說，如果這種情況 沒有得到滿足時，象是上等於false。 如果你只是將它理解 把假的另一邊？ 指導老師：是啊。 因此，實際上，如果你 曾經做的事情 象是上還是下， 返回true或false 它實際上是不好的風格 比方說等於等於true或等於 等於false。 要使用該結果 因為本身你的支票。 不是我想要的。 這就是我想要的。 所以，在你的情況你問 關於像保存在C。 

所以，如果我們有INT主要（無效） 而這樣的事情。 你有，如果是上 一些輸入你的 問如果你能做到 這樣的事情？ 對不對？ 學生：我是想 要做到這一點[聽不清]。 因為如果it's-- 指導老師：對。 所以，你希望這是假的，對不對？ 學生：是啊。 講師：所以在這種情況下，你 希望它執行的，如果它是不正確的。 所以，你在那裡做的很酷的事情是這樣的。 所以請記住驚嘆號 點否定的東西呢？ 它說[聽不清]表示不。 因此，如果我們看一下剛剛 這部分在這裡，你會 說，計算結果為 只要你想為false。 不是假的是真的， 這意味著將執行。 這是否有道理？ 學生：是啊。 講師：真棒。 行。 因此，我們可以只返回 真在這種情況下。 所以，現在我們有兩個 例在這種情況下。 什麼是我們的另外兩個情況？ 讓我們只是做這種方式。 所以，讓我們開始其他 如果在中間值 不到我們想要的值。 所以我們在中間的值小於 不是我們要尋找的價值。 

那麼，哪綁定你 我們認為要更新？ 上或下？ 上？ 因此，該陣列的一側 我們將要在看什麼？ 

學生：下部。 

教師：我們豈不是 可以看左邊。 所以，如果別人沒有什麼價值較少。 所以，你的中間值在這裡 不到我們想要的。 因此，我們要採取 右側我們的陣列。 所以，我們要 更新我們的下界。 因此，我們將重新分配我們的低。 那你覺得下應該是什麼？ 學生：中間值？ 講師：所以中間value-- 學生：加1。 講師：--plus 1。 誰能告訴我為什麼 我們有一個加1？ 

學生：[？沒有價值？] 更等於它。 

指導老師：對。 因為我們已經知道， 我們的中間值不等於 它和我們要排除 所有後續搜索。 如果你忘了加1，這 會喜歡無限循環。 而你只是陷入了 無限循環，然後你就會出現段錯誤 而事情變壞。 因此，始終確保你不 其中包括價值，你只是 看了看。 因此，我們照顧與加1。 

所以，現在我們有我們的最後一個條件 我總是為了安全著想 您可以點擊這裡，否則，如果在值 中間的是大於該值 我們想要的。 這意味著，我們要 左手一半。 那麼，哪一個我們要更新？ 上。 什麼是這個打算一樣的嗎？ 中間減1，因為， 當然，我們要 以確保我們不 再看那中間值。 然後，我們有它。 就是這樣。 這是所有的二進制搜索。 這並不是說不好，對不對？ 這就像10行 用空格代碼。 所以很強大，很實用，你會 在你以後的pset中的一個使用它。 也許不是這一個，但後來。 所以，學習它。 愛它。 它會善待你。 因此，沒有人有任何 在二進制搜索的問題？ 是。 

學生：它的問題 您是否n為偶數​​或奇數？ 

導師：第 因為我們投它中間的 一個int，它只會截斷。 所以它會留一個整數，它會 通過一切最終排序。 所以，你不必擔心。 大家好？ 真棒。 涼爽。 所以，你們得到這個。 幻燈片。 因此，當我們在談論，我知道 大衛提到的複雜的運行時間。 

因此，在最好的情況下，它只是 1，我們稱之為恆定時間。 誰能告訴我為什麼，可能是？ 什麼類型的場景會是意味著什麼？ 嗯。 

學生：[聽不清] first-- 講師：所以中間作為 我們來到了第一個元素，對不對？ 這樣的一個數組或 無論我們正在尋找的只是 正好是在中間嫌民建聯。 所以這是我們最好的情況。 你進入真正的問題，恐怕不是 要達到[聽不清]經常。 那麼我們最壞的情況？ 我們最糟的情況是日誌ñ。 並且，是因為有全 兩件事，我談到的權力。 

所以在最壞的情況下這將意味著 我們不得不砍了下來陣列 直到它是1的一個元素。 因此，我們不得不砍了下去一半 因為很多時候，我們可能會。 這就是為什麼它的日誌N，因為 你只是保持除以二。 所以假設，你的東西 要知道，如果你曾經 要使用二進制搜索。 你必須元素進行排序。 他們進行排序，因為 這是你唯一的出路 可以知道，如果你能 扔了出來一半。 

如果你有這個混亂的包包 號碼和你說， 好了，我要去檢查中間 號碼和我正在尋找數 小於說，我只是去 隨意扔掉一半。 你不會知道你的 在另一半的數字。 列表中的排序。 同樣，這可能是 要提前一點點， 但你需要有隨機訪問。 你需要能夠公正 去那個中間的元素。 如果你必須遍歷 通過什麼 或者你花額外的步驟 去了中間的元素， 它沒有日誌N了，因為 您要添加更多的工作了進去。 這將使一點 在兩週更有意義， 但我就是那種想要前言， 給你們一個什麼樣的想法 來。 但就是這兩種 重要的假設 你需要一個二進制名單。 請確保它的排序。 這是大個的 你們現在。 和我們能進入 我們各種各樣的休息。 所以4選擇產品類別泡沫， 插入，選擇和合併。 他們都很酷。 如果你們決定採取CS 124， 您將了解各種不爽。 如果你是一個XKCD風扇，有 是一個非常酷的漫畫有關 就像真的無效的種種，我 強烈建議你去看看。 其中之一是喜歡那種恐慌，這 就像是，哦，不，返回隨機數組。 關閉系統。 離開。 所以古怪的幽默總是好的。 

因此，沒有人記得那種 像只是一個總體思路 如何冒泡排序工作。 你還記得嗎？ 

學生：是啊。 

講師：大膽試試吧。 

學生：所以你要通過和 如果是做大，那麼你交換兩個。 

指導老師：嗯。 沒錯。 所以你只要遍歷。 您檢查兩個數字。 如果前一個比較大 比一算賬， 你只要將它們使得在 這樣一來所有的高數 氣泡向著列表的末尾向上 和所有的數字低泡下來。 

他有沒有告訴你傢伙很酷 音效分揀的視頻？ 這是一種很酷的。 所以羅伯特剛才說的，該算法 您在列表中只是一步， 交換相鄰的值 如果他們不正常。 然後自顧自地重複 直到你不作任何交換。 所以，還不錯吧？ 所以我們只需要一個簡單的例子在這裡。 所以，這是怎麼回事排序 他們按升序排列。 所以，當我們經過第一 時間，我們期待通過八個 六顯然不 為了我們交換它們。 

所以，看看下一個。 八，以4沒有。 交換它們。 然後8兩，交換它們。 在那裡，我們走了。 所以，你第一遍之後，你 知道你最多 將是一路 在頂部，因為它只是 要不斷地 比一切更大 它只是將泡沫 向上一路到底那裡。 這是否有道理給大家？ 涼爽。 

所以，接下來我們來看看我們的第二次。 6個和4，開關。 六兩，開關。 現在我們有為了幾件事情。 因此，對於每一個傳球，我們 讓我們的整個列表， 我們知道，像許多號碼 在年底將被排序。 所以我們做了第三次， 這是一個交換。 然後在我們的第四個 過去，我們是零插槽。 因此，我們知道，我們的 數組已排序。 

那就是大 與冒泡排序的事情。 我們知道，當我們 具有零掉期，即 意味著一切 是完整的訂單。 這是一種怎樣檢查。 因此，我們也要去泡代碼 排序也並不壞。 這些都不是那麼糟糕。 我知道他們看起來有點嚇人。 我知道，當我把 類，甚至當我 教的班 第一次，去年， 我當時想，我該怎麼辦呢？ 是有意義的理論，但 我們如何真正做到這一點？ 這就是為什麼我還不想走 通過與你們這裡的代碼。 所以，我有一個偽 對你們這段時間。 因此，只要記住這一點作為 我們要轉型了。 因此，我們有一些反了 讓我們的掉期交易的軌道， 因為我們需要確保 我們正在檢查。 我們遍歷整個數組 因為我們只是做了這個例子。 如果元素之前大於 之後，我們是在元素， 我們交換他們，我們增加我們的 計數器，因為只要我們交換， 我們要讓我們的櫃檯都知道。 有什麼問題嗎？ 有些事情似乎好笑在這裡。 學生：你設置計數器為零 每次經過循環？ 難道你不堅持下去 回零每次？ 講師：不一定。 那麼，什麼情況是我們經過這裡。 所以，做一段時間，記住，這 將執行一次沒有失敗。 因此，它會設置 計數器等於零， 然後，它會遍歷。 由於它遍歷， 它會更新計數器。 由於它更新計數器，當它完成， 當它到達數組的末尾， 如果我們的名單還沒有被排序， 計數器將被更新。 

那樣的話就檢查情況，並 說，OK，就是櫃檯大於零。 如果是，再這樣做。 要重置，這樣，當你 經過，計數器等於零。 如果你通過一個排序 陣，沒有什麼變化， 失敗了，你 返回的排序列表。 這是否有道理？ 學生：它可能在一點點。 講師：OK。 如果有任何其他 問題的出現​​。 是。 

學生：你會的功能 對於交換的元素呢？ 

講師：所以我們其實可以寫 如果我們現在要的權利。 涼爽。 所以，關於這一點，艾莉森是怎麼回事 切換回設備。 這將很有趣。 我們有我們的好 在這裡冒泡排序的事情。 所以，我已經做了騎自行車 通過該陣列。 我們有我們互換了 都等於零。 因此，我們要交換相鄰 元素，如果他們太過份了。 所以，第一件事，我們需要 做的是通過我們的數組遍歷。 

那麼，你如何認為我們也許 通過我們遍歷數組？ 我們有和我等於0。 我們希望我要少 大於n減1負ķ。 我會解釋說，在第二。 所以這是一個最優化在這些地方， 記得我每次傳球後是怎麼說的 通過數組我們 知道什麼是on-- 

打完一遍我們 知道這是排序。 經過兩道我們知道 這一切進行排序。 經過三關我們 知道的排序。 所以，我現在的迭代 通過陣列這裡， 是它確保只有走 通過我們所知道的是未排序的。 行？ 這只是一個優化。 你可以寫它只是天真 通過迭代的一切， 它只是需要更長的時間。 與此四環路是 一個不錯的優化 因為我們知道，以後每滿 通過數組迭代這裡， 喜歡這裡的每一個完整的循環，我們知道 一個多這些元素 在最後進行排序。 

所以我們不必擔心這些。 這是否有道理給大家？ 很酷的小把戲？ 因此，在這種情況下，如果 我們通過迭代， 我們知道，我們要檢查 數組n和n加1是為了。 行。 因此，這裡的偽代碼。 我們要檢查數組ñ 和N加1是為了。 那麼，什麼可能我們有嗎？ 這將是一些條件。 這將是如果一個。 

學生：如果array n是 比數組n​​與1少。 指導老師：嗯。 那麼，小於或大於。 學生：大於。 然後，我們要交換他們。 沒錯。 所以，現在我們進入有什麼 機制交換呢？ 因此，我們通過這個簡短去了， 一種交換功能的最後一周。 有誰還記得它是如何工作的？ 因此，我們不能只是重新分配，對不對？ 因為其中一人將得到丟失。 如果我們說，A等於B，然後B 等於A，突然兩個人 只是等於B. 

所以，我們要做的是我們 有一個臨時變量，是 將要舉辦的我們，而一個 我們在交換的過程中。 所以，我們所擁有的是我們有一些INT 溫度等於to--你可以指定它 到任何一個你想要的，只是 請確保你跟踪它 - 的 所以在這種情況下，我要去 它分配給數組n與1。 所以這是將要舉辦什麼 值是在該第二塊 我們正在尋找。 

然後我們可以做的是，我們可以去 提前並重新分配數組n與1， 因為我們知道，我們 有存儲該值。 這也是大的一個 things--我不知道你們中的任何 曾：如果你切換的兩個問題 代碼行突然事情的來龍去脈。 為了在CS非常重要的。 所以一定要確保你關係圖 事情是否可能 至於什麼是實際發生的事情。 所以，現在我們要 重新分配數組n與1， 因為我們知道，我們 有存儲該值。 

我們可以將它賦值給數組 在這種情況下，陣列I n或。 太多的變數。 行。 所以，現在我們已經重新分配數組我 加1等於什麼陣我。 現在我們可以回去 分配數組我的是什麼？ 任何人嗎？ 

學生：10。 

講師：10。 沒錯。 而最後一件事。 如果我們現在已經換了， 什麼，我們需要做什麼？ 什麼是一件事 這是怎麼回事告訴我們 如果我們終止這項計劃？ 什麼告訴我們 有一個排序的列表？ 如果我們不進行任何交換，對不對？ 如果互換等於 在此結束零。 所以每當你完成一個交換，因為我們 只是在這裡做，我們要更新掉。 我知道有一個 剛才的問題能左右你 用零次或一次，而不是 true或false。 而這正是這並不在這裡。 因此，這如果不是掉期說。 所以，如果掉期為零，這is--我總是 讓我的真理，我falses混淆。 我們希望我們能夠評估 以真實，事實並非如此。 所以，如果是零，那麼它是假的。 如果你有一個否定它 [？一聲？]成為事實。 那麼接下來這條線執行。 

真理與虛假， 零和一弄瘋了。 只是，如果你慢慢走 通過它它才有意義。 但是，這就是這個小 代碼位在這裡呢。 因此，這將檢查 我們做任何交換。 所以，如果它的任何東西，除了 零，這將是錯誤的 而整個事情是 要再次執行。 很酷吧？ 

學生：什麼突破呢？ 

講師：剛剛突破 打破你跳出循環。 所以在這種情況下，它會 只是想結束程序 而你只想 有你的排序列表。 學生：驚人的。 講師：對不起？ 學生：因為以前我們 用過寫1比寫零 提出，如果 將工作或沒有。 

指導老師：是啊。 所以，你可以返回零個或1。 在這種情況下，因為我們沒有真正 做什麼用的功能， 我們只是希望它打破。 我們真的不關心它。 剎車也不錯，如果 它是用於突破 四個環或條件的那 你不希望繼續執行。 它只是需要你了出來。 這是一個有點細微的事情。 我覺得有 很多擺手的， 就像你將了解這一聲。 

但是，你將了解這一聲。 我保證。 行。 因此，每個人都得到冒泡排序？ 差不太多。 遍歷，使用交換的東西 臨時變量，我們都設在那裡？ 涼爽。 真棒。 行。 回到PowerPoint文件。 一般來說任何問題 這些這麼遠嗎？ 涼爽。 嗯。 

學生：[聽不清]詮釋主通常。 你必須有這個？ 

講師：所以我們只是在尋找 只是在實際的排序算法。 如果你在有它 像一個更大的程序， 你將有一個int的主要地方。 這取決於你在哪裡 使用這種算法， 這將決定什麼 由它返回。 但對於我們而言，我們是嚴格 著眼於如何真正做這個 遍歷數組。 所以，我們並不擔心。 

因此，我們在談論最好的情況和 最壞的情況下為二進制搜索。 因此，這也是非常重要的做 對於每一個我們的排序。 所以你認為是什麼做的是最差的 冒泡排序的情況下運行？ 你們還記得嗎？ 

學生：N減1。 講師：N減1。 因此，這意味著有 ñ減1的比較。 所以，有一點認識是 即在第一次迭代中， 我們經歷，我們比較 這些two--所以這是1。 這兩個，三個，四個。 所以一次迭代後，我們 已經有四個比較。 當我說的是運行和n。 N表示比較的數量 有多少元素的函數 我們有。 行？ 

因此，我們過不去，我們有四個。 下一次當你知道我們不 要利用這一服務。 我們比較這兩個， 這兩個，這兩個， 如果我們沒有這個優化 與四循環，我寫的， 你會比較這裡反正。 所以，你必須 通過陣列上運行 而從N比較ñ 次，因為每次我們 運行通過它我們排序的一件事。 

每次我們通過運行時間 數組，我們從N比較。 因此，我們運行的是 實際上Ñ平方，其中 是更糟糕了 日誌末尾，因為這 也就是說，如果我們有四個 十億元素，它的 我們要花費four十億 平方，而不是32。 所以不是最好的運行時間， 但對於某些事情， 你知道，如果你是內 在一定範圍內的元素 冒泡排序可能會比較好用。 

行。 所以，現在什麼是最好的情況下運行？ 學生：零？ 還是1？ 

教師：那麼1人 是一次比較。 右。 

學生：N減1？ 

講師：所以，是的。 因此n減1。 當你有一個像N A概念 減去1，我們往往只是把它關閉 我們只說N，因為你有 比較每個these--每對。 所以它會為n減去1，這是我們 我們剛剛說的是大約ñ。 當你正在處理的運行時間， 一切都在接近。 只要指數是 正確的，你很不錯。 

這就是我們如何處理它。 所以，最好的情況下是n，這 意味著該列表已經排序， 而我們要做的就是通過運行 並檢查它的排序。 涼爽。 行。 所以，當你看到這裡，我們 只是有一些更多的圖形。 因此n的平方。 好玩的。 遠小於n更糟，因為我們看到了， 多，比數2n個糟糕得多。 然後你也進入日誌記錄。 你拿124，你進入 像日誌的明星，這是像瘋了似的。 所以，如果你有興趣， 查詢日誌的明星。 這是一種樂趣。 因此，我們有這個偉大的圖表。 只是抬起頭，這是一個 精彩圖有 為您的中期，因為我們 長問你這些變薄。 所以才抬起頭來，這個對你 對你的好小抄中期 那裡。 所以，我們只是看著冒泡排序。 最壞的情況下，N的平方，最好的情況下，N。 而且我們要看看其他人。 

正如你所看到的，唯一的 一個真正做得好 是歸併排序，我們將進入的原因。 所以我們要去的 下一個這裡 - 選擇排序。 有誰還記得 選擇排序工作？ 去了。 

學生：基本上經歷 一種秩序，創造一個新的列表。 而且，正如你把元素 中，把他們在正確的地方 在新的清單。 

講師：這樣的聲音 更像是插入排序。 但是你真的很近。 他們是非常相似的。 就算我讓他們混在一起的時候。 這部分我像以前一樣，等待。 行。 所以，你要 做的是選擇排序， 你能想到的方式 它和方式 我要確保我盡量不要讓 它們混合起來，是它通過 的情況下選擇 最小數目和它 提出，在列表的開頭。 它交換它與第一點。 他們居然對我有一個例子。 真棒。 所以，只是一個方式去思考它 - 選擇 排序，選擇最小的值。 而我們要 通過一個實例運行 我認為這將有助於因 我覺得視覺效果總是幫助。 因此，我們的東西開始了 這是完全無序。 紅會未排序的， 綠色進行排序。 它將所有的意義在第二。 

所以，我們通過我們遍歷 從開始到結束。 我們說好，2 我們最小的號碼。 因此，我們要採取2，我們要 將它移動到我們的數組的前面 因為它是 最小數，我們有。 所以，這就是這是在這裡做。 它只是要交換這兩個。 所以，現在我們有一個排序 部分和未分類的一部分。 什麼是好記 關於選擇排序 是我們唯一的選擇 從無序的一部分。 

排序的一部分，你只是獨自離開。 嗯？ 

學生：它是如何知道什麼是 最小無它比較 到陣列中的每一個其它值。 講師：它確實進行比較。 我們喜歡跳過它。 這只是一般的整體。 是啊。 當我們編寫我的代碼 相信你會更加滿意。 但是，你保存這第一 元件為最小。 你比較，你 說好，是不是更小？ 是。 保留它。 這裡是小？ 不是嗎？ 

這是你最小， 它重新分配給你的價值。 你會感到非常的快樂 當我們通過代碼。 因此，我們過不去，我們交換了，所以再 我們看一下這個排序的部分。 所以，我們要選擇三個出來。 我們打算把它在 我們的排序的部分的端部。 而我們只是要繼續做 這，做那，而這樣做。 因此，這是我們的一種偽這裡。 我們將在這裡編寫它在一秒鐘。 但只是一些走 通過在一個高的水平。 你會從去 i等於0到n減去​​2。 這是另一種優化。 不要太擔心了。 所以，當你在說什麼。 正如雅各說，我們​​怎麼 跟踪我們什麼是最小的？ 我們怎麼知道？ 我們來比較 一切都在我們的名單。 

因此，最小等於我。 它只是說，在這種情況下， 我們的最低值的索引。 這樣的話它會遍歷 而它從j為我加1。 因此，我們已經知道， 這是我們的第一個元素。 我們不必把它比作自己。 所以，我們開始把它比作下一個 1這就是為什麼它是我加1到n 減1，這是 陣列那裡的端部。 我們說，如果數組 j是小於陣列分鐘， 那麼，我們在那裡重新分配 我們的最低指標是。 

而如果分不等於i，如 在這裡我們又回到了這裡。 所以像我們當初做這個。 在這種情況下，它會開始 零，這將最終被兩人。 所以分也不會等於我到底。 讓我們知道， 我們需要交換它們。 我覺得自己像一個具體的例子 將幫助遠不止此。 因此，我將這個代碼與你們 現在，我認為這將是更好的。 

排序往往工作方式在 它往往只是為了更​​好地看到它們。 所以我們想要做的是 我們首先需要的最小 元件在它的陣列中的位置。 正是雅各說的話。 你需要存儲，不知怎的。 因此，我們要在這裡開始 遍歷數組。 我們會說這是我們的 第一次只是開始。 因此，我們將不得不INT 最小等於陣列在島 

所以，有一點要注意，每 這個時間循環執行， 我們開始一起又進了一步。 當我們開始我們看這一個。 接下來的時間，我們遍歷， 我們已經開始在這一個 而分配給它我們的最小值。 所以這是非常相似的冒泡排序 我們知道，一個傳球後， 這最後一個元素進行排序。 與選擇排序， 它正好相反。 

在每一個傳球，我們知道， 第一個是排序。 第二次通過後，將 第二個將被排序。 正如你看到的幻燈片的例子， 我們來分類的部分只是不斷增長。 因此，通過設置我們最小的一個 到數組我，所有它做 收縮是什麼 我們正在尋找這樣 最小化的數量 比較我們做。 這是否有意義大家？ 你需要我通過運行 再慢，或者在不同的話嗎？ 我很高興。 行。 

因此，我們的存儲 在這點上的值， 但是我們也希望來存儲索引。 所以我們要保存 最小的位置 1，這是只是要我。 所以，現在雅各是滿意的。 我們所儲存的東西。 現在我們需要看看通過 陣列的未分類的一部分。 所以在這種情況下，這 將是我們未排序的。 這就是我。 行。 

所以，我們要做些什麼 將是一個循環。 每當你需要 遍歷數組， 你的頭腦會去為一個循環。 因此，對於一些INTķ equals--什麼，我們認為 k被要等於開始？ 這是我們設置了最小 價值，我們要進行比較。 我們究竟要比較它？ 這將是該下一個，對不對？ 所以我們要k，進而進行初始化 要我加1開始。 

我們希望K的這種情況下，我們 已經存儲的大小在這裡， 所以我們可以只使用尺寸。 大小作為數組的大小。 我們只是想 一，每次更新ķ。 涼爽。 所以，現在我們需要找到 這裡的最小元素。 因此，如果我們遍歷，我們 想說，如果數組日K 小於我們最小value-- 這就是我們實際上 跟踪是什麼 最小這裡 -  那麼我們要重新分配 就是我們最小的值是。 

這意味著，哦，我們是 迭代經過這裡。 無論值是這裡 不是我們最小的事情。 我們不希望它。 我們要重新分配它。 所以，如果我們要重新分配它，做什麼 你覺得可能是這裡的代碼？ 我們要重新分配 最小的位置。 還等什麼，現在是最小的？ 學生：列K。 講師：列K。 是什麼位置呢？ 什麼的指數 我們最小的價值？ 它只是ķ。 所以列K中，k，它們相匹配。 因此，我們要重新分配。 再之後，我們發現我們最小的， 因此在今年年底for循環 在這裡我們找到了我們的最小 值，所以我們只是換了。 在這種情況下，像說我們的 最小值是出在這裡。 這是我們的最小值。 

我們只是想在這裡交換，這是 是什麼在底部的交換功能 的確，這是我們剛剛寫了 同時幾分鐘前。 所以它應該很熟悉。 然後它只會重複 通過直到它到達一路 到結束，這意味著你 具有零個元素是無序 和其他一切已排序。 有意義嗎？ 有一點更具體？ 該代碼的幫助？ 

學生：對於一個規模，你永遠不 真正定義它或改變它， 它是怎麼知道的？ 

教師：那麼一回事， 注意在這裡為int的大小。 所以我們說在這個類別 - 排序 是在這樣的函數case--它 選擇排序，它通過 同的功能。 所以，如果它沒有通過 中，你會做什麼 像與所述陣列的長度 或者你會遍歷 找到的長度。 但由於它的傳遞 中，我們可以只使用它。 你剛才假設​​用戶 給你一個有效的尺寸 實際上代表 一個大小的數組。 很酷吧？ 

如果你們有這些任何麻煩 還是要多練編碼排序 在你自己的，你應該 去study.cs50。 這是一個工具。 他們有一個檢查器 你其實可以寫。 他們這樣做偽。 他們有更多的視頻和幻燈片 包括那些我在這裡使用。 所以，如果你仍然感覺 有點模糊，嘗試了這一點。 與往常一樣，來和我說話了。 問題？ 

學生：你說的 大小是預先定義的？ 指導老師：是的。 大小是預先定義了 這裡的函數聲明。 所以，你認為它已經通過了 由用戶，並且為簡單起見， 我們將假設 用戶給了我們正確的大小。 涼爽。 所以這是選擇排序。 伙計們，我知道我們今天學習了很多。 這是一個密集的數據部分。 於是就這樣，我們將 去插入排序。 

行。 所以，在這之前，我們需要做的 我們這裡的運行時分析。 所以，在最好的情況下， 理所當然，因為我給你 表我已經 種就將它丟棄。 但是，最好的情況下運行時，我們會怎麼想？ 一切都來分類的。 Ñ​​平方。 任何人都有一個解釋 為什麼你覺得呢？ 

學生：你比較through-- 指導老師：對。 你比較過。 在每一次迭代中，即使 我們正在遞減這一個， 你還在尋找通過 一切都找到了最小的一個。 所以，即使你的最小值 就是在這裡開始， 你還在比較其 反對一切 以確保它是最小的事情。 所以，你最終會通過運行 大約ñ平方倍。 行。 什麼是最糟糕的情況？ 也可為N的平方，因為你會 在做了同樣的過程。 所以在這種情況下，選擇 排序有什麼 我們也呼籲預期運行。 因此，在別人，我們只知道 的上限和下限。 這取決於如何瘋狂我們 列表或者如何排序的是， 它們n或n的平方之間變化。 我們不知道。 

但由於選擇排序有相同的 最壞和最好的情況下，這告訴我們， 無論輸入什麼類型的，我們 有，無論是完全 排序或完全 反向排序，這是 要採取的相同的時間量。 因此，在這種情況下，如果 從表中我們還記得， 它實際上有一個值，該值 這兩類沒有， 這是預期運行。 所以我們知道，每當 我們運行選擇排序， 它保證 運行一個n的平方時間。 沒有可變性存在。 這只是預期。 並再次，如果你想學習 更多的，拿CS 124的春天。 行。 我們已經看到了這一點。 涼爽。 所以插入排序。 而且我可能會 走出一條通過此。 我不會有你們編寫它。 我們將步行穿過它。 所以插入排序是怎麼樣 類似於選擇排序 在我們有兩個未排序 和排序的陣列的一部分。 

但不同的是， 因為我們通過一個接一個， 我們只取什麼數 接下來是我們未排序的， 並正確排序 到我們的排序的數組。 它會更有意義，用一個例子。 所以一切開始作為未分類， 只是想用選擇排序。 而我們要在此排序 升序因為我們一直。 因此，我們第一遍 我們採取的第一個值 我們說好，你是 現在在列表中自己。 

因為你是在一個列表 由自己，你的排序。 恭喜您成為了 此數組第一個元素。 你已經排序的所有靠自己了。 所以，現在我們有一個排序 和一個未排序的數組。 所以，現在我們採​​取的第一個。 在此之間會發生什麼 這裡就是我們說的， OK，我們要去看看 我們排序的數組的第一個值 而且我們要投入在其 正確的位置排序數組中。 

所以，我們要做的是，我們採取5 我們說好，5大於3， 所以我們只是將它的權利 到的，該權利。 我們是很好的。 那麼接下來，我們繼續我們的下一個。 我們採取2。 我們說好，2少 比3，所以我們知道它 需要是在 我們的名單前面了。 所以，我們做的是我們推3和5下 我們提出2成第一個插槽。 所以，我們只是將其插入 正確的位置是應該的。 

然後我們來看看我們的 下一個，我們說6。 行，6大於 一切都在我們的排序的數組， 所以我們只是將其標記到結束。 然後我們來看看4。 圖4是小於6，就少 比5，但它是大於3。 所以我們只是把它插入到正確的 3和5之間的中間。 因此，為了使這一點 多一點具體的， 這裡是怎麼樣的 想法發生了什麼事。 因此，對於每一個未排序的元素，我們 確定在排序部分 它是。 

所以，牢記 分類和未分類， 我們已經遍歷和數字 出它的排序的數組能容納。 我們通過移動插入 元素，它的降權。 然後，我們只是不停 通過迭代，直到我們 有一個完全排序的列表 其中，無序現在是零 和排序佔用 我們的全部名單。 所以，再一次，為了讓事情 更具體的，我們有偽代碼。 

所以基本上對我是 等於0到n減1， 這是我們陣中僅有的長度。 我們有一些元件，它等於 第一陣列或第一索引。 我們集合的J相等。 因此，雖然j大於 零和陣列，J減去1 大於 元素，讓所有的做 為確保 您Ĵ真正代表 陣列的未分類的部分。 

因此，儘管還有事 排序和j減一is--什麼 是她的元素？ J以從來沒有在這裡定義。 這是一種煩人。 行。 反正。 所以Ĵ減1，你檢查 之前的元素。 你說，OK，是元素 之前，無論我am--我們 實際繪製了這一點。 所以我們可以說，這是 就像我們的第二次。 所以我將是相等 為1，這是在這裡。 

所以我將是等於1。 這將是2，4，5，6，7。 行。 因此，我們在這種情況下，元素 將是等於4。 我們有一些Ĵ這 將等於1。 哦，j被遞減。 那它是什麼。 所以j等於我，所以這個是什麼 說的是，我們向前邁進， 我們只是要確保 我們不是在 索引這樣，當我們試圖 插入的東西到我們的排序列表。 

因此，當j等於1在這種情況下，與 陣列Ĵ減埃德蒙頓所以數組Ĵ減1 2本case--如果這就是 大於所述元件， 那麼這一切是做 被轉移下來。 所以在這種情況下，陣列Ĵ減一 將陣列為零，這是2。 圖2為不大於4， 所以這不會執行。 這樣的移位，並不會向下移動。 這裡做的事情在這裡只是 移動你的排序的數組下來。 在這種情況下，實際上，我們 可以do--讓我們做這3。 所以，如果我們穿行與 這個例子，我們現在在這裡。 這是排序。 這是未排序的。 很酷吧？ 所以i等於2，所以 我們的元素等於3。 與我們的j等於2。 因此，我們期待通過我們 說好，是數組Ĵ減一 大於所述元件 那我們看什麼？ 答案是肯定的，對不對？ 圖4是大於3和j 是2，那麼該代碼執行。 

所以，現在我們做的一個數組 2，所以在這裡，我們交換它們。 所以，我們只是說，OK，陣列 2，現在將是3。 和j是要等於 Ĵ減1，為1。 這是可怕的，但 你們的想法。 J是現在等於1。 和陣列j的只是要 等於我們的元件，​​為4。 我刪除的東西我不應該 有或miswrote東西， 但是你們的想法。 

它移動以n。 然後，如果這是，它會循環 再次，它會說，OK，j是1了。 和陣列Ĵ減1現在是2。 2小於我們的元素？ 不是嗎？ 這意味著，我們已經 插入這個元素 在我們排序的數組中的正確位置。 然後，我們就可以利用這個和我們說， OK，我們的排序的數組是在這裡。 它會採取這個數字6，並 就像，OK，比這個數少6？ 不是嗎？ 涼爽。 我們很好。 

再次這樣做。 我們說7。 比所述端部7少 我們的排序的數組？ 號 所以，我們很好。 所以這將被排序。 基本上，這一切確實 它是在說拿 的第一個元素 您排序的數組， 找出通向哪裡 在排序的數組。 而這只是照顧 掉期來做到這一點。 你基本上只是交換 直到它在正確的位置。 視覺形象是你 移動都記錄下來做的。 

所以，這就像半冒泡排序式的。 退房研究50。 我強烈建議嘗試 編寫這個你自己。 如果您有任何問題，或者您想 參見示例代碼插入排序， 請告訴我。 我總是四處。 因此，最壞的情況下運行 和最好的情況下運行。 當你的傢伙從表中看到，我已經 表現出你，這既是ñ平方和n。 

種這麼打算過什麼，我們聊 關於我們以前的種種，最糟糕的 情況下運行時，如果 它是完全不排序， 我們必須比較所有這些n次。 我們做了一大堆的比較 因為如果它以相反的順序， 我們會說，OK，這 是相同的，這是很好的， 而這一次將要被比較 相對於第一個要被移動回。 而且隨著我們走向 尾部，我們有 比較，比較和 與之比較的一切。 

因此它最終被 大約Ñ平方。 如果它是正確的，那麼你 說好，2，你是​​好。 3，你比2。 你很厲害。 4，你只是比較的尾巴。 你很厲害。 6，比較的尾巴，你的罰款。 因此，對於每一個點，如果它已經 排序，你正在做一次比較。 所以它只是ñ。 因為我們有最好的情況下運行 n及n的最壞情況的運行時的 方，我們也沒有預期的運行。 

這只是取決於 亂我們的名單中出現。 又一次，另一 圖形和另一個表。 所以各種各樣的差異。 我只是微風過，我 感覺我們已經談過了廣泛 有關他們都怎麼樣 的變化，並且連接到一起。 所以合併排序是最後一個 我要你承擔傢伙。 我們也有一個漂亮的多彩畫卷。 所以，歸併排序是遞歸算法。 所以，不要你們知道是什麼 遞歸函數是？ 

任何想說的？ 你想試試嗎？ 因此，一個遞歸函數就是 一個函數調用自身。 所以，如果你們熟悉 與斐波那契序列， 該公司認為，因為遞歸 你把前面的兩個 並把它們相加 讓你的下一個。 這樣循環，我一直認為 遞歸如像​​一個螺旋形的 所以你像螺旋式下降了進去。 但它只是一個功能 調用自身。 

而且，實際上，真的很快我 可以告訴你那是什麼樣子。 所以遞歸這裡，如果我們看，這是 遞歸的方式來總結一個數組。 因此，所有我們要做的就是 我們有求和函數 總之，需要一個大小和數組。 如果你注意到，大小 減一各一次。 和所有它的作用是，如果x等於 zero--因此，如果該數組的大小 等於zero--返回零。 

否則，這個總結 所述陣列的最後一個元素， 然後採取的總和 該陣列的其餘部分。 所以它只是將它分解 成越來越小的問題。 長話短說，遞歸， 函數調用自身。 如果這是你離開了這一點， 這就是一個遞歸函數。 如果你51，你會得到非常， 很舒服的遞歸。 這真的很酷。 它以有意義像 上午03點一晚了。 我當時想，為什麼 我也從來沒有用這個？ 

因此，對於歸併排序，基本上 什麼是要做的是它的 要打破它，打破它 直到它只是單一的元素。 單個元件​​很容易就可以進行排序。 我們看到這一點。 如果你有一個元素，它的 已經考慮排序。 等n個元素的一個輸入端， 如果n小於2， 剛回來，因為那意味著 它是0或1，因為我們已經看到了。 那些被認為是排序的元素。 

否則，打破它的一半。 排序上半年，排序第二 一半，然後將它們合併在一起。 為什麼它被稱為歸併排序。 所以，我們在這裡，我們將整理這些。 因此，我們繼續讓他們 直到數組大小為1。 所以，當它的1，我們只返回 因為這是一個排序後的數組， 這是一個排序的數組，而這 一個排序的數組，我們都來分類的。 那麼接下來我們要做的是我們 啟動它們合併在一起。 

所以，這樣就可以 想想合併是 你只是刪除小 各子陣列中的數 而只是將其追加到數組中出現。 所以，如果你看看這裡，當我們有 這些集我們有​​4,6和1。 當我們要合併這些， 我們看一下前兩個 我們說好，1越小， 它會向前方。 4和6，有沒有什麼比較 它，只是將其標記上到結束。 

當我們結合這兩個，我們只是 取這兩個中較小的一個， 所以它的1。 現在我們採​​取的 這兩個，所以2的小。 這兩個，3個較小的。 這兩個，4，5，6以下。 所以，你剛才拉過這些。 而且由於他們把 以前被排序， 你只有一個 比較有各一次。 因此，更多的代碼在這裡，只是表示。 所以你在開始，中間和 您排序左右 然後你只要這些合併。 

我們沒有代碼 對於合併就在這裡。 但是，再說一次，如果你去上 研究50，它會在那裡。 否則，來跟我說話 如果你還在迷茫。 因此，這裡很酷的事情是最好的情況下， 最壞的情況下，與預期的運行時 都在日誌中N，其中 遠不如我們已經 看到了我們各種各樣的休息。 我們已經看到ñ平方 而其實我們 拿到這裡的n log N，這是偉大的。 

看看這是多麼要好的多。 這樣一個漂亮的曲線。 因此，更有效。 如果你可以，使用歸併排序。 這將節省您的時間。 話又說回來，正如我們所說的，如果 你倒在這個較低的地區， 它不會作出這樣的 多大的差別。 你得到多達數千 和數以千計的投入， 你一定要一個 更有效的算法。 並再次，我們可愛的表 各種各樣，你們今天學到。 

所以，我知道這是一個密集的一天。 這不一定要去 幫助您與您的PSET。 但我只想做一個免責聲明 該節不只是pset中。 所有這些材料是公平的 遊戲中為你的期中考試。 而且如果你繼續用CS， 這些都是非常重要的基礎 你需要知道的。 所以，有些日子將是一個 多一點PSET的幫助， 但幾個星期會 更多的實際內容 這似乎並不超 現在對你有用， 但如果你繼續我答應 上會非常，非常有用。 

所以這是它的一節。 下來的電線。 我做了一分鐘之內。 但你去那裡。 我也有甜甜圈或糖果。 有沒有人過敏 任何事情，順便？ 雞蛋和牛奶。 因此，甜甜圈是一個沒有？ 行。 行。 巧克力不？ 星爆。 星形圖案都不錯。 行。 我們將有 下週爆吧。 這就是我去拿。 你們有一個偉大的一周。 看了你的天賦。 

讓我知道，如果你有任何問題。 PSET兩個檔次應該是 出來你在週四。 如果您有任何問題 我是如何分級的事情 為什麼我的東西漸變的方式，我 沒有，請給我發電子郵件，來和我說話。 我有點瘋了這 一周，但我保證 我仍然會在24小時內回复。 所以，有一個偉大的一周，每一個人。 祝你PSET。