[Powered by Google Translate] [第3] [舒適]
>> 內特 - 哈迪森] [哈佛大學]
>> 這是CS50。[CS50.TV]
>> 好吧，讓我們開始吧。
歡迎CS50 4週。
如果你們打開Web瀏覽器和打開的pset 3，
爭奪與CS50，我們要開始
通過的部分的問題存在。
就像上週，我們將工作在CS50空間，
，如果你也拉，以及，
如果你繼續前進，請訪問此鏈接，我已經起身在頂部。
現在是時候開始瀏覽網頁。
我們有我們的小喜這裡的程序。沒有什麼神秘的。
我想你們今天做的第一件事情就是去了幾個解決方案
問題1，種示例解決方案，
只是，這樣你可以得到什麼樣的代碼的工作人員正在寫一個感覺，
什麼樣的代碼其他學生寫作，
你看看它，因為我知道它的怪異
當您提交問題集的解決方案，並獲得評論
你自己的版本，但有時它是有益的，看看其他人如何做，
尤其是很不錯的期待。
在大多數情況下，我真的很感動，你們生產的解決方案。
我還沒有開始看習題集2，但如果他們是什麼第一，
這意味著什麼，但好東西。
>> 如果你看一下我的修改，讓我們開始一路下跌，在第1次修訂，
我們將採取一個快速的看看馬里奧解決方案的。
如果你拉這件事，我們會提出這些程序是正確的。
有沒有這些問題的正確性問題，而是
我們要談一點點的不同的設計問題
被用在這裡。
的事情，這是有趣的解決方案之一
是，它使用這個新的構造稱為磅的定義，
有時也被稱為作為一個哈希定義。
讓我在這裡放大。
A＃定義允許您給這些數字在你的程序中。
在這種情況下，它的最大高度在Mario金字塔
為23，而不是把23在我的代碼
我們將參照硬編碼23 -
提供的名稱，而不是MAX_HEIGHT這個數字，
所以，在這裡我do-whil​​e循環
實際上，你可以參考MAX_HEIGHT
而不是把號碼23英寸
[學生]：這樣做的優點是什麼？
這是一個很大的問題。
一個是可讀性。
使用此＃定義的優點是可讀性。
當我讀這段代碼中，可以看到發生了什麼事情。
>> 我在這裡可以看到，在這種情況下，我們正在測試
的高度，即<0，我們也可以定義
是最低限度的高度或最低高度。
另一個好處是，我可以讀取行的其餘部分
我們還在檢查，以確保高度不大於最大高度，
因為我們要繼續下去，而高度大於最大高度。
另一個好處是，如果我放大了一點點
如果我運行這個程序，我運行它，說，現在有23，
它會打印出23行一樣，。
但說我想改變的最大高度，
現在我想限制的最大高度金字塔
只能說人，那是時髦的。
＃包括，定義MAX_HEIGHT，
讓我們說，我們要設置它等於10。
現在，在這一點上，所有我需要做的是改變它在這一個位置。
我可以重新編譯代碼，現在如果我嘗試輸入12，
它會提示我了。
在這種情況下，我們只用MAX_HEIGHT一次。
這並不是說大的麻煩去
並改變它在while循環中，如果你需要的話。
但是，在您在何處引用了相同的幻數的程序
一遍又一遍，這樣的機制是非常方便的
因為你只需要改變一個時間的文件，它通常你把他們的頂端
和變化滲濾通過文件的其餘部分。
>> 其他的事情，我想指出，我認為在這個任務看起來真的很不錯，
一個是變量的命名。
你在這裡看到的，我們已經有了整數變量稱為行，所謂的高度。
空間，哈希，它有助於使代碼更具可讀性一點，
多一點理解什麼實際事情。
這是在對比使用，也就是說，隨機字母
或只是官樣文章完全。
最後記住一件事，我要指出的是，在for循環中，
通常這些迭代器變量，計數器，您在您的循環使用，
它的標準和傳統的開始，我和那麼j，則k
從那裡，如果你需要更多的變數，
這僅僅是一個慣例。
有很多的公約。
這取決於你使用的編程語言。
但在C中，我們通常開始與我同在。
使用它沒有意義，也就是說，a或b
視情況而定。
這是這一個。
如果你現在拉了第二次修訂，你會看到一個馬里奧，
而這一次是我們剛剛看到另一個類似，
但它確實挺酷的東西。
如果我們看一下在本節內內循環，
他們使用的是一些瘋狂的尋找在此行中的語法在這裡。
這就是所謂的三元運算符。
這是一個if else語句，凝結成一條線。
條件是這部分括號內。
這相當於說，如果j <高度 - 我 - 1。
然後的內容是什麼，如果塊的空間
然後將內容的else將＃。
它本質上是一個空間分配給這個變量。
它把一個空間中的內容的塊變量，
如果滿足此條件，如果該條件沒有被滿足，
然後塊變量得到＃。
然後，當然，而不是建立整個字符串
印刷一切結束時，該解決方案把它打印出一個字符的時間。
很酷。
>> 另外一對夫婦的事情來看待。我們將要討論的貪婪。
現在，如果我們看貪婪，這第一個解決方案
使用＃定義相當多的。
我們已經有了一個常量定義在這個程序的每一個不同的數字。
我們已經有了一個美分美元，一個季度，助攻，鎳，和便士，
現在如果我們向下滾動和閱讀代碼，
我們可以看到一個標準的do-whil​​e循環打印了。
一種意識到這個問題的癥結所在，
你需要轉換的浮動，你在閱讀的用戶整數
準確地做數學題，這是因為
浮點數字，就像我們在演講中簡要地談到，
這是不可能的，準確地反映每一個價值數行
因為有無窮多個值之間，並說，甚至3.1。
你可以有3.01和3.001及3.0001，你可以繼續下去。
事實證明，用錢時，你的工作，你經常需要將其轉換
轉換為整數，所以你不會失去便士和諸如此類的東西。
這樣做，和舍入是關鍵。
該解決方案使用了一個完全直接的，巨大的算法，
遞減數剩餘美分，第一季度，
然後通過硬幣，然後由鎳，然後通過便士，
和添加的硬幣的數目，每次。
>> 另一種解決方案，我們會看到，我縮小到4修訂版，
有一個非常類似的開始，而是採用div和mod
在這裡的數量來計算美分。
這樣，宿舍的數量是等於除以25美分的數量，
這個工作的原因是因為我們正在做整數除法，
所以它丟棄任何剩餘的。
[學生]：我們要不要發表評論，搜索嗎？
這真的視情況而定。
[學生]：你註釋以上代碼就在這裡。
是啊，所以有一堆不同的哲學。
我的個人哲學是你的代碼是真正的真理，
喜歡你的代碼是什麼實際的計算機上執行，
所以你的代碼應該盡可能地易讀沒有必要了許多意見。
這就是說，當你正在做的事情，是一種棘手的數學
或算法，這是很好的評論，這樣就可以
誰是閱讀你的代碼中添加一個額外的維度，一個額外的層。
在這些解決方案中，他們往往更多地只是因為被註釋掉
我們希望能夠分發給才有人接他們時，
讀他們很容易。
但可以肯定的是，我同意，這是沉重的。
[學生]：但是，當疑問，請重？
如果有疑問，去重了。
有時，有些人會說，返回0或類似的東西。
我認為這是一個荒謬的評論。
顯然，這是發生了什麼。
我不需要英語告訴我。
有時候人們會寫的東西像​​“kthxbai！”
這是種可愛，但也未
這不是評論點或不之間的差異。
這些類型的評論是，哈哈哈。
酷。
>> 在這一點上，讓我們開始工作的習題集3節的問題。
如果你們拉起來了，
與上週一樣，我們不打算在本節觀看短褲。
我們將讓你們這樣做對你自己的時間和談論的問題。
但是，現在在本節中，我們將要花費多一點的時間
談論的編碼基礎
像我們一樣上週，而不是，我們會更專注於
多一點點的理論，所以在談論二進制搜索和排序。
你已經遵循了演講，
有人可以給我一個概括的區別是什麼
之間的二進制搜索和線性搜索？
這是怎麼回事呢？當然。
線性搜索可通過在排序列表中的每一個元素
一個由一個一個逐個
二進制搜索將列表分為2組，
檢查，如果你正在尋找的關鍵值，大於或小於中間值
你剛剛發現的，如果是小於，它會與下面的列表中
然後將再次做同樣的功能
一路下來，直到它找到中點，等於本身的價值。
右。
>> 我們為什麼要關心？
我們為什麼要談論與線性搜索的二進制搜索？
是啊。
二進制是快了很多，所以如果你的問題的規模增加一倍
它需要一個步驟，而不是兩倍多。
沒錯。
這是一個偉大的答案。
線性搜索是非常檢查在一個時間，一個元件
正如我們所看到的第一天的演講
當大衛•多姆德（David Drummond）通過他的手機，書中的例子
一次撕開了一個頁的電話本
並不停地一遍又一遍，再這樣做，
它要帶他在電話簿中找到任何的很長一段時間，
除非，當然，他要找的人在一開始的字母。
在二進制搜索，你可以去快了很多，
它不只是兩次以最快的速度或快3倍或4倍的速度。
但是，問題變得更小和更小的和更小的要快得多。
為了說明這一點，我們就開始談論這是怎麼回事
當我們寫二進制搜索。
目前的問題是，如果我有一個數組的數字，
說，1，2，3，5，7，23，45，78，12323，
然後一噸的0後，
我們希望能夠真的很快弄清楚什麼是
這個數組。
我知道這似乎有點傻，有點做作，
因為現在它是。
我們有一個數組，沒有很多的元素在裡面，
如果我問你是否找出
23是在數組中，你能做到這一點很快
只是掃了一眼，告訴我“是”或“否”。
要考慮的是模擬想像一下，如果這個份上，說，
一個Excel電子表格有10000行，20000行。
當然，你可以執行命令F或控制F，看的東西了。
您還可以使用過濾器和搜索的東西，
但如果你有看通過該文件中的行由行線，
它會花費你很長的時間來找到它。
這是一種在電話簿的例子一樣，太，其中
沒有人期待通過一次的電話簿1頁。
通常情況下，他們開到中間，
或在的情況下，大量的電話本和字典
你實際上它的第一個字母鍵，
你翻轉，第一個字母，打開並開始經過那裡。
>> 再次提醒我你的名字。>>山姆。
山姆。
像Sam說，該線性搜索過程將是很慢的，
，而不是二進制搜索的工作方式是，
我們每次去通過我們的搜索算法的迭代，
我們要分一半的列表中，基本上，
成兩個較小的列表。
然後在循環的下一次迭代，我們將其劃分再
進入其他較小列表。
正如你可以看到，這個問題繼續變得更小和更小的
因為我們保持每一次放棄一半的列表。
丟棄它是如何工作？
正如一個提醒，我們要做的，如果我們的電腦
和我們說，在此列表中，尋找5號
是，我們會選擇一個中間的數字。
在此列表中，因為有1，2，3，4，5，6，7，8，9，10的號碼，
我們會選擇在第4位或第5位，
我們會打電話給我們的名單中。
選擇在中間。
然後，就像山姆說，我們將測試一下，看看如果這個數字是相等的
的數量，我們希望得到我們想要的號碼。
如果相等的話，我們已經找到了。我們贏了。
如果不相等，則有一對夫婦的情況下。
這兩種情況是數數大於我們正在尋找，
或者是小於。
如果是更大的，我們移動到右邊。
如果是，我們移動到左側。
然後，我們再次重複整個過程，
右半或列表中的左半邊。
>> 在今天的部分的第一個問題是要弄清楚
實際上，我們可以在C代碼中開始表達。
我們在這裡得到的偽。
我們將開始做的是我拉了一個全新的空間，
保存本次修訂，使我們有這些說明後，
我們將刪除所有這一切，然後複製並粘貼問題集
此信息進入我們的空間，並希望這不會打破。
完美的。
如果你們都這樣做，這段代碼複製並粘貼到新的空間，
進入一個空白。
讓我們嘗試丹尼爾。如果你編譯並運行這個程序，它的工作嗎？
號>>什麼是它在說什麼？
它說，控制到達非void函數的結束。
是啊，所以我嘗試運行它。
你們見過嗎？你知道這意味著什麼嗎？
好吧，讓我們來剖析這一點點。
它說在file.c在第9行，第1列，我們有一個錯誤，就像你說的，
它說，它源於錯誤警告和返回類型的警告。
它看起來喜歡的東西是怎麼回事，這是有道理的返回類型。
我們有一個非void函數，這意味著我們已經有了一個功能
不返回void。
一個void函數，是一個看起來是這樣的：
無效的foo（），它是無效的，因為返回類型為void，
這意味著，如果我們有一些東西在這裡
如返回1，我們會得到一個編譯錯誤。
但是，我們有一個非void函數。
在這種情況下，我們的非void函數是我們的搜索功能
因為它有一個返回布爾類型的。
當它的控制達到了一個非void函數，
這是因為搜索沒有一個return語句。
它沒有返回bool類型的任何東西。
>> 我們可以解決這個問題，你們怎麼想
搜索返回的默認？
搜索默認的返回值應該是什麼？
因為這是我們可以放在最後。
夏洛特，你有什麼？
真還是假的？>> TRUE或FALSE。
哪一個？
為False。我不知道。
假的？讓我們試試吧。
為什麼你會說，返回假的？這是偉大的直覺。
[夏洛特]我不知道。
我們將返回false，在這種情況下，因為這將是我們的默認
如果由於某種原因，該列表為空，或針
我們正在尋找不存在的。
然後在最後，如果我們不返回true早些時候在這個函數中，
我們一直知道，這個函數會說，不，這不是在數組中。
這不是在草堆裡。
現在，如果我們要編譯和運行它讓我節省，所以我們可以把它拽上來。
現在，如果我們要編譯和運行我們的程序，它的基礎之上。
我們得到了我們的小提示。
如果我打了4架UH-OH。
它沒有打印出任何東西。它看起來像一切結束行。
我們必須填寫此英寸
我們談到了該算法的偽代碼一點點。
讓我看看，保存，
，我會拉算法備份。
讓我們來打這傢伙。不。
在那裡，它是。
如何才能做到這一點呢？
這將是一個很好的策略開始這段代碼嗎？
你必須選擇一個中間的數字。
我們如何在一個數組中挑選一些呢？
有什麼建議嗎？
[學生]：STRLEN除以2。
STRLEN除以2。這是一個偉大的。
strlen的作品特殊類型的數組。
什麼類型的數組？
String數組，字符數組。
這是同樣的概念，我們要申請，
但我們不能使用strlen，因為我們沒有一個字符數組。
我們有一個整型數組。
但到底是什麼strlen的我們嗎？
你知道它會為我們嗎？
[學生]：STRLEN讓我們長。
沒錯，它使我們的長度。
STRLEN得到我們的數組的長度。
>> 我們怎樣才能在我們的二進制搜索程序？
你會得到一個數組的長度？
[學生]：STRLEN？
你可以得到一個正確格式化C字符串數組的長度與strlen的。
，不過，問題是，我們沒有一個字符串數組。
如果我們回頭看這段代碼，我們有這樣的整數數組。
我們怎麼知道它有多長？
[學生]：是否有一個相當於一個端點，如INT L或什麼的？
事實證明，實際上不是，因此，在某種程度上，這是
這些事情，只是知道關於C之一，
有沒有辦法讓一個數組的長度
如果我給你的是一個數組。
它的工作原理與字符串的原因，因為strlen的作品，
是因為如果一個字符串格式是否正確，
它會特別在最後的\ 0字符。
>> 您也可以設想一下，如果你有一個格式不正確的字符串
有沒有\ 0字符，那麼整個事情並沒有工作。
[學生]：你可以添加\ 0？
我們可以在這種情況下。
我們可以添加某種\ 0
或某種標誌著字符，然後使用它。
但是，這不太去上班
因為\ 0是一個char類型，
在這裡，我們有整數。
另一件事是，如果我們要使用一個特殊的值
像-1，以紀念數組末尾
然後，我們永遠無法在我們的整數數組存儲-1。
我們希望被卡住了。
事實證明，只有這樣，才能得到長度
實際上是一個數組在C記得它
當你設置它，然後把它傳遞的陣列
所以，每當我有一個函數，會做一些工作
數組的整數或浮點數或雙打，你有什麼，
我還需要給函數的數組的長度，
這正是我們在這裡所做的搜索功能。
如果你看一下，我們做了什麼，當我們通過在我們的數組，
我們還通過在長度，尺寸。
這恰好是我們把這種現象稱之為變量，
此參數或參數。
這就是所謂的一個函數的參數列表或參數列表，
這些也稱為參數或參數。
人們在不同的時間使用不同的術語。
我有時會交換他們自己。
碰巧的是，這裡被命名為這個變量同樣
這定義在這裡。
但他們不一樣的東西。
資本化也很重要。
>> 如果你看看這裡發生的事情，我們聲明
我們的int數組，這是我們所撥打的電話號碼。
我們已經給我們的規模，這相當於我們的＃定義在最頂端。
這將是8。
然後當我們再調用我們的搜索功能，下面，
我們通過我們要搜索的數量，我們已經提示，
從用戶得到。
我們通過在陣列中，這個號碼，
然後我們還必須通過在數組的大小，
，然後該值被存儲大小為8
或傳遞給這個整數變量稱為大小。
我們有陣列的大小。
現在，如果我們回到我們在談論什麼較早，
我覺得大小姐長大一點，我們需要做的是得到數組的長度
除以2，這將使我們的中點。
讓我們來看看。
我有別人寫這篇文章，並將其保存在自己的空間呢？
萊拉怎麼樣？
我能有你寫這篇文章？
寫的第一行，你把數組的長度，得到的中點
並將其存儲在一個新的變量。
我給你幾秒鐘。你準備好了麼？
[學生聽不清]
當然，我有你計算的中點
幹草堆數組裡面的搜索功能
用幹草堆陣列的長度，這是變量的大小？
這裡沒有什麼棘手的。
萊拉]大小/ 2和剛剛
並保存它，並點擊“保存”按鈕，在頂部上升，
我們會拉起來。
完美的。
我們走吧。真棒。
>> 是，編譯？
[萊拉]沒有，它需要的要高。
[內特]是啊，所以我們需要做什麼？
[萊拉，如int的中點或什麼的。
真棒。是啊，讓我們做到這一點，中點=大小。
編譯？
讓我們刪除這條評論，並把它弄出來的方式。
究竟會不會編譯這件事？
我們不會做任何事情的整數，
因此，我們需要打印或類似的東西。
是的，沒錯。
我們會得到一個未使用的變量。
還有什麼工作呢？
我想你說了些什麼，山姆。分號。
是的，我缺少的分號。
這將是一個常數事情的整個過程的術語。
我會做的最後一件事是，我把一些白色的空間，任何一方
運營商在這裡，因為這通常是如何做到這一點
根據我們的風格指南。
我們有我們的數組的中點。
現在，如果我們還記得我們的算法，
第二步，我們不得不這樣做，一旦我們有中點是什麼？
[學生]：如果它是大於[聽不清]。
是啊，所以我們必須做一些比較，我們比較什麼？
你說，如果它是大於。這是什麼那句話指的是？
的數量，來了，如果這是大於中點，然後去到數組？
沒錯，這樣的數字出現時，我們
針，所以我們比較針，
什麼是我們比較針嗎？
因為針是我們要尋找的是什麼。
我們在比較得到的中點。
>> 但它是有意義的檢查，看看
如果針=的中點？
這是否有意義嗎？
是否有人不同意嗎？
讓我們給它一個嘗試，如果（針==中點）。
[學生]：printf的你發現了它。
[內特的printf（“我們發現了！\ n”）;
否則，我要開始做不同的東西在這裡。
我要開始把周圍所有的時間if語句的大括號
只是因為，如果我們添加更多的東西，然後
我們沒有得到的編譯器。
是啊，山姆。你已經有了一個點。
的問題是，中點表示在數組中的位置，
但你可以得到它代表的價值在這個位置上的數組。
這是一個很好的點。
大家聽到山姆說什麼？
他說，中點是
只是在數組中的位置，但它不是實際的數組中的元素。
如果你寫的代碼現在想想，
如果我們看一下這裡，在這個數組有8個元素在裡面，
中點要在這個函數中的價值是什麼？
[學生]：4。
[內特] 4。
如果我們看一下數4 -
，我們可以運行此代碼，在這裡放一點點悲傷的臉
因為我們沒有找到它，如果我們運行這個代碼
是現在，上傳，建築，讓我向下滾動，
如果我們看看數4，
我們發現了它，但我們沒有得到這個輸出是。
其中一個原因是，我們並沒有返回true，
但當時我們真的找到4？
和Sam說“不”。
我們發現了什麼？
我們真的找到了中點，如果我們看一下在陣列在這裡，
這將是指數4，我們正在尋找的元素，
這是23。
>> 我們如何真正得到該元素的中點
不只是中點本身嗎？
[學生]：我們將輸入字符或什麼的？
那麼，具體怎麼做，只是出於好奇嗎？
你能否解釋一下嗎？
您的位置轉換成數，
所以你不得不做出一定的聯繫，我認為這是char，但它可能不是。
是的，這是一個很好的點。
我們已經做了很多這種轉換位置的字符，這些字符，
前兩個問題集。
事實證明，在這裡，這幾乎是類似的
訪問第i個字符在字符串中，如果是有道理的。
在這裡，我們要訪問的中點元素。
我們如何做到這一點？
凱文，你有什麼建議，我們怎麼可能做到這一點？
你可以做幹草堆，開括號，中，右括號。
你可以寫我們嗎？
將它保存在這裡，我們會拉，直至。
我們正在尋找在該行9，
我們意識到，我們不想比較針的中點，
但相反，我們要比較的針
位置中點我們的草垛陣列內的元素。
酷。
我們走吧。
是的，這看起來很不錯，如果（針==草垛[中點]）。
我們發現了它。
現在，如果我們運行的代碼 - 我們將備份一點點，
編譯，運行，現在如果我們看一下4，
我們沒有找到它，因為現在我們實際上獲得的23號。
我們現在要值23，這是我們比較我們的針。
但是，這是很好的。這是朝著正確的方向邁出的一步。
>> 這就是我們想要做的。
我們並不試圖對數組中的位置比較針
而是針對實際的數組中的元素。
如果我們現在再回頭看我們的算法中的下一個步驟，
下一步是什麼？
萊拉已經提到了簡要介紹。
[學生]：檢查，看它是否大於或小於，然後決定哪個方向移動。
[內特]是啊，所以我們會做什麼？
你可以把一些 - 我本次修訂，
然後，如果你把在一些線路，將這樣做。
是啊，夏洛特。>>我有一個問題。
難道不應該的第一件事就是中點 - 1，因為
它的0索引，因此，如果我們把4，其實這不是我們要找的字符？
是的，和其他的問題，即-
這是一個偉大的漁獲量，因為正在發生的事情可能發生
如果我們繼續前進，我們永遠不調整初始嗎？
我猜我們可能最終做的是試圖訪問
在第8位的數組元素，
在這種情況下不存在。
我們會想要做某種會計的事實
我們有一些零的索引。
[夏洛特]對不起，我的意思是在方括號中的中點 - 1。
我們可以做到這一點。
我們會回來的這個問題，在短短位。
一旦我們開始得到了實際的循環，
那個時候，我們真的會看到這是發揮。
就目前而言，我們可以做到這一點，但你是完全正確的。
零索引將產生影響，我們需要考慮的。
讓我們來看看。
>> 如何大於和小於？
[學生]：我要怎麼弄了大於和小於部分。
我只是不知道，如果你發現這是不到的草垛中點或大於打印內容。
在這裡，我可以節省難不倒我，
[內特]是啊，如果你保存你有什麼，我們就會把它。
我們走吧。
[學生]：我把問號是什麼我不知道。
內特 - 這看上去很不錯。
在這裡，我們已經得到了問號，因為我們仍然不知道
我們要完全做到。
我們希望，做哎呀，我們已經得到了一些大括號對我們的所有時髦的。
我們會糾正這些大括號。
我們走吧。
還等什麼，我們想要做的，按照我們的算法，
如果我們沒有發現針？
的情況下，說針是小於我們正在尋找。凱文。
只有看的左半邊。
對，所以我們會把在這裡評論說：“看在左半邊。”
如果針是大於幹草堆的中點處，我們想要做的嗎？
[學生]：那你看右半邊。
看右半邊，“看右半邊。”
不能太寒酸。
好了，所以在這一點上，東西都看起來相當不錯。
寫的代碼的問題是什麼？
[學生]：您沒有終點的一半。
是的，我們沒有端點的一半。
此外，我們也只有通過這一次要去。
我們只是要在一個中點。
無論是元素是存在的，或者它不是。
為了完成這一目標，我們需要做某種形式的重複。
我們需要不斷重複，直到我們找到
無論是元素，因為我們已經縮小，終於找到了，
，或者它不是在那裡，因為我們已經看遍了所有的事情，
在適當半的陣列，發現在那裡，沒有什麼是。
>> 每當我們已經有了這樣的重複，那我們該怎麼使用？
[學生]：一個循環。
某種形式的循環。是。
[學生]：我們可以做一個do-whil​​e循環，有它這樣做，然後，
針不相等的，我不知道我要去哪裡與。
但有點像做，只要它不等於的值，用戶輸入。
是啊，所以讓我們來看看，這怎麼可能寫出來嗎？
你說讓我們使用一個do-whil​​e循環。
在什麼地方開始？
[學生]右後大小/ 2。
[內特]好吧，什麼是我們該怎麼辦？
我們將填寫後的一段時間。
什麼是我們該怎麼辦？
[學生]：你不是我們想要做的所有的東西，我們如果部分嗎？
[內特]做了這一切東西，太棒了。
複製和粘貼。
哦，男人。
讓我們來看看，如果這個工程，如果我們能“選項卡這種過度。
美麗的。
好了，我們保存，這樣你們。
所有權利，我們將做到這一點，而
而條件後是什麼？
[學生]：當針不相等的，所以像驚嘆號。
但我不知道到底是什麼還。
[內特]是啊，這是一個辦法做到這一點。
山姆，你有意見嗎？
[三]我記得當我看著影片，
我的截圖之一，像我們做的偽代碼時，
最大值和最小值之間有一定的關係。
我認為這是類似的東西如果max是永遠小於min。
明白了。
[三]想，如果最大不小於分鐘或類似的東西，
因為這將意味著，您搜索過的一切。
>> 是啊，所以它聽起來像最大值和最小值是指？
[三]，整數的值，要改變
相對於我們把中點。
沒錯。
[三]在這一點上，它是怎麼回事[聽不清]計算的最大值和最小值。
中點這是最大和最小的想法。
這是否有意義人嗎？
如果我們要開始找我們要如何做到這一點迭代，
你是完全正確的，我們要使用某種do-whil​​e循環。
但我想，如果我們還記得發生了什麼事在這個數組當場
，什麼是實際發生的事情，我會寫在這裡
在第一次迭代的二進制搜索，我們有
我要使用b和e來表示開始。
我們的陣列，然後結束。
我們知道，開始的時候是在4對在這裡，
我們知道，到底是在108。
說，我們正在尋找的15號。
當我們第一次這樣做，就像我們前面看到的，
中點將是16或23
這取決於我們如何計算的事情了。
由於等分的中間，給我們這個空間
在16和23之間，我們不能整除它
或者將其與一個真正的中點。
我們將在16歲。
我們將實現“嘿，16> 15，我們正在尋找的。”
然後看陣列的左半邊
我們最終會做什麼是丟棄
這整個上部
並說：“好了，現在我們的終點會到這裡來。”
我們的循環的下一個迭代的，我們現在看這個數組，
有效地捨棄這部分，因為現在
如果我們的中點的開始和結束之間的差異，
我們發現我們的中點為8，
然後，我們可以測試，看看它是關係到我們正在尋找數，
15日，有15個是更大的，
所以我們必須要移動到列表中的右邊部分，
我們知道，因為我們是人類，我們可以看到它。
我們知道，右側部分將是我們在那裡找到它，
但電腦不知道這一點，所以我們要做的是，我們實際上
已經上去了，現在開始和結束
是相同的點的中點，所以成為在這一點上的列表中的唯一編號，
這是15日，我們已經找到了。
這是否透露​​了一些關於這整個的最大和最小的符號是怎麼回事，
跟踪的端點的數組，以便找出
如何縮小東西下來？
>> 如果這是不等於15，會發生什麼？
如果我們一直在尋找，這個數字是15，而不是16嗎？
我們會說，“哦，這是更大的。
我們要回去的左邊。“
我們將我們的電子的權利，
在這一點上，我們有一個端點，是相互矛盾的。
這不會是能夠搜索到任何更多的元素
因為現在我們有我們的端點和我們的起點，
我們的最大和我們的分，現在翻轉。
我們搜索整個陣列。我們無法找到任何東西。
這一點上，我們會說，“好了，我們要制止這種算法。
我們沒有發現任何東西。我們知道這是不是在這裡。“
這是怎麼回事呢？
[學生]：電腦的開關究竟是如何結束了嗎？
如何結束前開始嗎？
結束前開始
因為，我們要做的每次我們這樣做的數學。
我們交換的方式是，如果你的第一次，我們這樣做交換
在那裡我們有在4的開頭和結尾
所有的方式，在108和我們的中點，也就是說，在16 -
我要重置回15，如果我們正在尋找的15個，
我們知道我們做了什麼，當我們檢查了16看到，這是更大的
想放棄整個右半部分的列表，
我們看到什麼，我們想要做的是將這個電子就在這裡。
實際上，電子轉移到了之前的中點。
同樣，當我們這樣做的算法迭代
和中點是在8，
我們發現，8 <15，所以我們希望移動的b
過去的中點。
現在，始端和末端都在這15一起。
>> 如果我們已經發生的事情，尋找一些其他的價值，而不是15，
如果這15而不是16，
我們會發現，E，我們要移動前的中點。
電子翻轉少於B。
讓我們通過我們實際上如何結束這種編碼算法。
我們知道，我們希望有這樣的中點計算。
我們也知道，我們要跟踪的開頭和結尾的數組
我們目前的陣列，所以我們可以計算出
這個列表的左半和右半列表。
我們做到這一點的開始和結束，
或者我們可以給他們打電話的最小值和最大值。
我將使用開始和結束時間。
當我們開始之前，如果我們回頭看，我們的例子中，在這裡，
我們一開始就被設定為一開始的數組，是自然的。
什麼樣的指標是這樣的嗎？我們開始可以嗎？
丹尼爾。
[丹尼爾]的幹草堆[0]。
[內特]是啊，所以我們可以設置它等於幹草堆[0]。
，不過，問題是，這給我們的第一個元素的位置。
它給我們的第一個元素或實際值，第一個位置的索引。
[學生]：這將轉換為0.20？
內特 - 這將是孔，它不會做任何的皈依。
它會做的，是將存儲4開始，
那麼這將是很難進行比較，對開始
因為BEGIN將持有的價值4，
這是我們的數組的開始，
但我們要跟踪的指數數組中的
相反的值。
實際上，我們將使用0，這樣的。
對於最終的陣列夏洛特帶來了這起得更早一點。
這是我們會考慮到零的索引。
>> 夏洛特，什麼是數組末尾的嗎？
什麼是指數結束？
[夏洛特] - 1。
是啊，它的大小，我們應該使用？
我們應該使用資金規模或小寫的大小？
資本的大小。
在這種情況下，我們可以利用資金規模。
如果我們希望這個函數是可移植的
在其他程序中使用此功能，
實際上，我們可以使用小寫字母的大小。
這是一件好事。
但夏洛特是完全正確的，我們希望有大小 - 1。
在這點
[學生]：它是如何，你可以使用大寫的大小嗎？
它是如何，我們可以使用大寫的大小嗎？
事實證明，這些＃定義是真的，
引擎蓋下，一個文本，如查找和替換，如果是有道理的。
當你編譯你的代碼，預處理階段
編譯器通過文件，
它看起來無處不在，你寫的資金規模，
它取代這些文字的字面與8，就這樣。
從這個意義上說，這是非常不同的變量。
它不佔用任何內存空間。
這是一個簡單的文本替換技巧。
在這種情況下，我們將要使用的大小。
在這裡，我們想這樣做某種形式的重複，
我們在正確的軌道上，與我們的do-whil​​e循環。
我們想要做的事，直到條件不成立了，
正如我們前面所看到的，我們看到，該條件
的確，我們不希望最終
是小於的開始。
>> 這是我們的停止條件。
如果發生這種情況，我們要停止，並宣布，“嘿，我們沒有發現任何東西。”
為了表達這一點，我們要使用某種形式的循環。
在這種情況下，它是一個do-whil​​e循環，for循環，while循環？
在這裡我們有一個do-whil​​e循環。
你們這樣的方法嗎？
你認為我們應該嘗試不同的方法嗎？
凱文，有什麼想法嗎？
我們可以有一個while循環，因為我們知道最大
將比開始不管怎麼說分鐘。
是啊，所以沒有初始化，需要做的。
這些do-whil​​e循環是偉大的，當你要初始化的東西
在此之前的測試，而在這裡
我們知道，我們不打算再繼續重新初始化開始和結束
每一輪的循環。
我們知道，我們要對其進行初始化，然後檢查我們的條件。
在這種情況下，實際上，我會用一個簡單的while循環中去。
事實證明，do-whil​​e循環是相當不經常使用。
很多地方甚至不教不while循環。
他們是很好的處理用戶輸入，因此迄今為止我們已經看到了很多人。
但正常的，while循環，也有很多比較常見的。
事實證明，這種情況書面
不會真的對我們很有好處，這是為什麼呢？
對不起，我不知道你的名字。
我傑里。>>對不起嗎？
這是B-O-R-U-I。
哦，好吧。
我看不到你，我的名單上。
哦，這是因為，哦，這是有道理的。
你有一個想法，這個while循環的原因可能無法按預期，
寫的條件嗎？
[傑里，你的意思是你想要的所有東西後，它的？
是啊，所以這是一個。
我們可能需要把所有的這些東西進入while循環，這是完全正確的。
其他的事情，不過，這是一個有點比較麻煩的是，這種情況不工作。
[學生]：您需要翻轉。
對，所以這種情況將不會是真實的最初因為我們談論的方式。
我們想要做的事，直到結束<開始，
但我們想要做的東西，而
開始≤年底。
>> 還有，反轉的邏輯。
我犯了這些錯誤的時間。
[學生]：為什麼必須小於或等於？
因為你還記得的情況下，我們得到了
那裡只有一個元素，我們比下降，
我們正在尋找在數組中的15？
我們的開始和結束都是一樣的元素。
我們要確保我們處理這種情況。
如果我們做了一個直不到，
我們將只能得到2個元素的數組。
一旦我們得到了下來，最後一個元素，如果這是我們的元素，我們永遠也找不到它。
現在，在這裡，我們可以做的正是像你說的話。
我們可以開始撲通東西，到我們的while循環中。
我們可以撲通一聲在我們的中點。
我們可以把所有這些if語句，
將它們拉出來的這do-whil​​e循環，
撲通一聲，
乾淨的東西一點點，
，我會繼續保存本次修訂。
在這一點上，我們已經很接近了。
山姆。
我想你也必須有int中點，=大小 - 1/2。
明白了，大小 - 1/2。
我們需要改變該行的還有什麼呢？
這是一個很好的漁獲物。
>> 大小做什麼呢？我們不斷變化的大小嗎？
為了保持這樣的線，我們要改變的大小。
我們每次去周圍的循環，我們必須改變大小。
但是，請記住，當我們將通過我們的例子只是一點點，
我們開始在4
結束在108一路過來嗎？
我們是如何計算的中點？
我們使用的大小？
我們使用的開始和結束，而不是嗎？
它的結束和開始之間的差異。
沒錯，究竟如何，我應該寫，夏洛特？
剛剛結束“ - ”開始“。
你不會需要做的 - 1
因為 - 1已包含在最終並已開始。
[內特]太好了，你是完全正確的。
我們沒有做 - 1 - 1已被列入
並佔當我們初始化結束變量。
>> 還有什麼我需要做的語法有這條線是有意義嗎？
[學生]：加開始。加上開始的呢？
[學生]：在最後。
因為它只是計算一​​半的長度。
您需要添加的開始。
[內特]這算什麼我們？
如果我們想結束這個循環迭代，
到底是怎麼回事，是在第7的位置索引。
開始的位置為0。
請記住，我們正在尋找任何
位置3或4的位置。
如果我們看一下這道數學，只是為了使這一點更有形，
在這裡把一些數字，我們有7，0，
7 - 0，然後/ 2
3整數除法，那是。
那麼我們需要再添加回我們的開始嗎？
在這種情況下，我們不。
在第一次迭代中，這將是罰款，因為BEGIN為0。
但是，我們的進步，我們真的只需要
結束 - 開始/ 2。
這裡還有另外一個絕招，那就是即一個優先級。
[學生]：我們需要括號？
[內特]沒錯，這是因為，如果我們不把這些括號，
那麼這條線將被解釋，而不是
（完） - （開始/ 2），這是我們絕對不希望。
對於那些優先級規則。
[學生]：為什麼不是結束+開始的呢？
為什麼它沒有結束“+”開始“？
[學生]：為什麼不說？
為什麼會+？
我想你是對的。
[學生]：因為它的平均？
[內特]末開始，你是完全正確的。
哇，我完全弄錯了。你說得對。
如果我們在做減，我們將要添加的開始。互動式
在這種情況下，你是非常正確的，我們要採取平均兩個，
所以我們要加入他們，而不是減去它們。
[學生]：這也將工作，如果你真的結束 - 開始/ 2 +開始。
如果我們這樣做，我相信。
>> 例如，如果我們在開始時，
而我們這裡轉移，
15。
現在開始在位置2。
到底是在第7位。
如果我們減去它們，我們可以得到5。
除以2，得2。
然後，我們加2，
並因此獲得第4的位置，
就在這裡，這是中點。
[學生]：我們需要照顧的包裝嗎？
在何種意義上，我們需要照顧的包裝嗎？
如果總和或之間的區別
這取決於我們如何做到這一點是不是偶數。
然後，計算機會感到困惑是否當的2.5;
你移動到左邊或有權決定的中點？
明白了。
事實證明，與整數除法，
我們永遠不要讓這些浮點數。
我們從來沒有得到小數。
這是完全丟棄。
如果你有一台電腦分兩個int變量，
一個是7，和另一個是2，
你不會得到3.5的結果。
它會得到3。
其餘部分將被丟棄，所以它是有效的舍入
不是圓形，而是一個樓層，如果你們是熟悉的，在數學，
你完全放棄小數，
所以你基本上截斷它下調至最接近的
整個位置，最接近的整數。
[學生]：但是，這是有問題的，因為如果你有7個元素的數組
然後，自動將第三個元素的中點，而不是第4。
我們該如何處理呢？
這是有問題的，因為如果我們有一個數組中的7，
它會選擇，而不是第3第4。
你能解釋一下嗎？
[學生]：因為如果你有7個元素，那麼第4個元素
的中點，對不對？
零的索引，請記住您的評論。
[學生]：是的，所以在位置3。這將是中點。
是啊。
哦，好吧。我明白你的意思。
這是一種奇怪的，因為我們習慣了這整個概念
擺脫小數。
這是一個很好的點。
讓我們來完成這件事。
我們計算過我們的中點。
>> 我們正在測試，看看我們的針是等於中間值。
我們要打印，我們發現了它，但說真的，在這種情況下，我們想要做的是什麼呢？
我們已經找到了，所以我們希望讓來電者知道，我們發現它。
我們已經有了一個功能，是一個布爾類型的函數。
WE信號的方式向我們的函數的調用者，我們已經準備好
我們說：“嘿，這是真的。”
我們將如何做到這一點，凱文？
你點頭你的頭。>> [凱文]返回true。
[內特]沒錯，返回true。
現在，如果它是不相等的，怎麼會看的左半邊嗎？
有什麼想法？
斯特拉，任何想法？
您需要設置一個新的位置結束。
是啊。
所以，我們要做的中點位置 - 結束。
大。
我們需要建立一個新的位置結束
看的左半邊。
這就是我們談到了之前在那裡
我要回這個例子。
我已經在這裡開始，然後我結束所有來這裡的路上。
>> 同樣，如果我們要找的15，我們的中點是在16，
我們認識到，“哎呀，16。
我們要移動到左邊的一半。“
然後，我們將移動到15月底，
我們這樣做的一個距離的中點
並設置作為我們新的結束。
同樣，如果我們想看看在適當的一半，如何將我們做到這一點呢？
你有一個想法？
[學生]：您剛才設置開始的中點+ 1。
[內特大。
現在的情況，我們沒有發現任何東西，
得到悉心照顧我們嗎？
丹尼爾，這是否得到照顧我們嗎？
[丹尼爾]第
[內特]如果我們把整個數組，我們沒有發現任何東西，
，照顧，我們還是應該照顧？
[丹尼爾]，而條件。
[內特]是啊，while條件，準確。
如果我們沒有發現任何東西，它會照顧整個數組。
這個while循環將結束。
我們從來沒有遇到過這種狀況，
我們可以返回false。
我們也可以離開這一點，如果這樣的在這裡
因為如果這個說法是正確的，
和我們函數將返回，
因此，我們將基本上取消該功能，在這一點上
當我們返回true。
但這種結構會發生什麼呢？
這項工作完全，或者是有一些邏輯上的缺陷在那裡？
>> 在那裡有一些邏輯上的缺陷，它的設立的方式。
它可能是什麼？
[學生]：為什麼你需要 - 和+ 1秒？
我們的陣列設置，是我們新的左半部和右半。
[學生]：但是，為什麼你不能做到這一點不 - 1和+ 1秒？
[內特]我們可以設置它等於中點？
有關，可能是什麼問題？
[學生]：我想這是低效的，因為你正在檢查已檢查的值的。
[內特]沒錯，所以山姆是完全正確的。
如果您設置的結束和開始的中點
- 1 + 1沉思，
在一些點在未來，我們將最終再次檢查的中點。
[學生]：我開始在pset，然後我有類似的東西
我忘了+ 1，它被卡在一個無限循環。
是的，因為在某些時候，你永遠不會得到的開始和結束
實際上是重疊的。
酷。
還有一個更合乎邏輯的缺陷，那就是，這絕對是
一個else if。
為什麼會這樣呢？
>> 原因是如果它不是別的，如果你看到它，凱文？
[凱文]是啊，因為你改變的終點。
[內特]沒錯。
我們正在改變端點，
，如果它寫這樣我們就會使空間之間的
它會檢查這種情況。
這種情況下，如果成功，將中止的功能。
然後，它會檢查這個情況下，
如果成功，將調整的終結點，
，然後它會繼續檢查這種情況。
但在這一點上，我們不希望它繼續檢查。
幸運的是，我們還沒有復位的中點，
我們知道，這種情況下是不會得逞的。
但是，我們一定要在那裡把其他
即使可能在這種情況下，
因為我們沒有調整的中點，這區別嗎？
沒有，因為這些情況都是排斥的。
再次，是我不好。
我們不這樣做，我想，否則，如果需要這個。
我們可以給它一個嘗試，並運行它，並看看會發生什麼。
大廈發生了錯誤。
這可能是因為我在這裡這些B和E的。
我還有更多的人高達頂部？
它看起來並不像它。
我們要放大，建造，
就這樣吧，所以現在如果我們搜索15，
是。
讓我放大。
15，是的。我們可以再次運行它。
上載的源代碼，構建，運行。
這樣的事情，我們可以搜索13，
和我們沒有得到任何打印出來的，所以它不是發現了這一點。
這是偉大的，因為它不是在我們的名單。
>> 我們現在沒有時間了。
這將是這個星期。
感謝您的加盟，看你以後。
>> [CS50.TV]