[音樂播放] 

ZAMYLA陳：首先，你可能會 通知有關的發現是，我們已經 已編寫的代碼我們。 這就是所謂的分配的代碼。 所以，我們不只是編寫我們自己的 從頭開始編寫代碼了。 相反，我們正在填補空隙 在某些預先存在的代碼。 

該find.c程序會提示輸入數字 填補了草垛，搜索 在haystack一個用戶提交的針， 它是通過調用排序和 定義的搜索，函數 在helpers.c。 所以find.c已經寫入。 你的任務是寫傭工。 

所以我們在做什麼？ 我們正在實施兩種功能。 搜索，返回true，如果一個值 在草垛被發現，返回 假如果該值 不是在幹草堆。 然後我們也實施排序 這所謂的排序值數組。 

因此，讓我們來解決搜索。 搜索當前實現為 線性搜索，但你可以做很多 比這更好。 線性搜索，現為O實現 n個時間，這是相當緩慢的。 雖然，它可以搜索 給它的任何列表。 你的任務是實現二分查找， 已運行日誌的n時間為O。 這是相當快的。 

但是有一個規定。 二進制搜索只能搜索 通過預排序的列表。 這是為什麼？ 

那麼讓我們來看一個例子。 給定的值的數組，草垛， 我們要去尋找 了針。 並且在該示例中， 整數3。 二進制搜索的工作方式是， 我們比較的中間值 陣列到針，很像如何 我們開了一個電話簿中間 在零一周頁面。 

所以中間值相比較之後 針，你可以放棄任 左或陣列的右半 收緊你的界限。 在這種情況下，由於3，我們的針， 小於10，中間值，該 右邊界會降低。 但盡量讓你的界限 盡可能緊。 如果中間值不是針 那麼你知道，你並不需要 它包含在你的搜索。 所以，你是對的綁定可以收緊 搜索範圍更多的只是一點點， 等等等等，直到 你發現你的針。 

那麼什麼是偽代碼是什麼樣子？ 好了，而我們仍然在尋找通過 列表中，仍然有元素 看在，我們把列表的中間， 而且中間值比較 我們的針。 如果他們是平等的，那麼這意味著我們已經 發現了針，我們可以 返回true。 

否則，如果針小於 的中間值，那麼這意味著我們 可以丟棄的右半邊，只是 搜索數組的左側。 否則，我們將搜索 右側的數組。 並在結束時，如果你沒有任何 留下來搜索更多的元素，但你 有沒有發現你的針還沒有，那麼你 返回false，因為針 絕對不是在草堆。 

現在，一個整潔的事關於這個偽代碼 在二分搜索的是，它可以是 解釋為一種迭代 或遞歸實現。 因此，這將是遞歸的，如果你叫 在搜索中的搜索功能 功能上無論是數組的一半。 在一個稍後我們將介紹遞歸 當然，但知道它是一個 如果你想嘗試的選擇。 

現在，讓我們來看看排序。 排序需要一個數組和整數 n，它是該數組的大小。 現在有各種不同類型的 不爽，你可以看一些 短褲的演示和講解。 返回類型我們 排序功能是無效的。 這樣就意味著我們不會 從排序返回任何數組。 我們究竟要改很 被傳遞到我們的數組。 

那是可能的，因為數組是 通過在C引用傳遞現在，我們將 看到後面會詳細講解，但 通過本質區別 在像整數和傳球 在一個數組中，就是當你 傳遞一個整數，C只是要 使該整數的副本，並通過 它的功能。 原來的變量不會被改變 一旦該功能被完成。 與陣列，在另一方面，它的 不會讓一個副本，你會 其實是可以編輯的 很數組本身。 

所以，一種類型的排序是 選擇排序。 選擇排序的工作原理是在開始 開始的時候，然後你遍歷 在找到的最小元素。 然後你換了最小 元件與所述第一1。 然後移動到第二個元素 ，找到下一個最小的 元素，然後交換與該 陣列中的第二個因素，因為 第一個元素已經排序。 所以，你繼續為每 在確定的最小元素 價值和交換出來。 

對於我等於0，第一個元素 到n減1，你要比較 之後，每一個未來的價值，並找到 最小值的索引。 一旦你找到的最小值指數， 您可以交換數組的值 最小和數組一 

另一種類型的排序，你可以 落實是冒泡排序。 因此，冒泡排序遍歷列表 比較相鄰元素和 交換的元素 是在錯誤的順序。 並且以此方式，最大元件 將泡沫到底。 和列表進行排序，一旦沒有更多的 元素已經被調換。 

因此，這些都是樣的兩個例子 您可以為實現算法 find程序。 一旦您完成排序，而你 做搜索，你就完蛋了。 我的名字是Zamyla，這是CS50。 

[音樂播放]