>> [音樂播放]
>> 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。
>> [音樂播放]