[Powered by Google Translate] [Phần 3] [Ít thoải mái] 

[Nate hardison] [Đại học Harvard] 

[Đây là CS50.] [CS50.TV] 

Được rồi, hãy bắt đầu. Chào mừng bạn đến với Tuần 4 CS50. Nếu bạn mở một trình duyệt web và mở ra pset 3, Scramble với CS50, chúng ta sẽ bắt đầu đi thông qua phần câu hỏi đó. Cũng giống như tuần trước, chúng tôi sẽ được làm việc trong CS50 Spaces, nếu bạn cũng sẽ kéo đó là tốt, và nếu bạn đi trước và truy cập vào liên kết này mà tôi đã có ở đầu trang. Đó là thời gian để bắt đầu. Chúng tôi đã có chương trình hi nhỏ của chúng tôi ở đây. Không có gì điên. Một trong những điều đầu tiên tôi muốn làm với các bạn ngày hôm nay là đi qua một số giải pháp Vấn đề Set 1, loại của các giải pháp ví dụ, chỉ để bạn có thể nhận được một cảm giác về những gì các loại của các nhân viên mã được viết, những loại sinh viên mã khác đang viết, và có bạn có một cái nhìn vào nó vì tôi biết nó là lạ khi bạn gửi một giải pháp cho vấn đề một tập hợp và lấy ý kiến trên phiên bản riêng của bạn, nhưng đôi khi nó là hữu ích để xem làm thế nào những người khác đã làm nó, đặc biệt là những người được tốt đẹp. Đối với hầu hết các phần, tôi đã thực sự ấn tượng với các giải pháp mà các bạn sản xuất. Tôi vẫn chưa bắt đầu nhìn 2s Set Vấn đề của bạn, nhưng nếu họ bất cứ điều gì như là người đầu tiên, nó có nghĩa là gì, nhưng những điều tốt đẹp. 

Nếu bạn nhìn vào các phiên bản của tôi, hãy bắt đầu tất cả các con đường xuống Revision 1, và chúng ta sẽ có một cái nhìn nhanh chóng tại một giải pháp Mario. Nếu bạn kéo lên này, các chương trình mà chúng ta sẽ trình bày là chính xác. Không có vấn đề đúng đắn với những vấn đề này, nhưng là, chúng tôi muốn nói một chút về vấn đề thiết kế khác nhau được sử dụng ở đây. Một trong những điều thú vị về giải pháp là nó được sử dụng xây dựng này mới được gọi là bảng xác định, đôi khi cũng được gọi là một băm xác định. Hãy để tôi phóng to, thu nhỏ về nó ở đây. # Xác định cho phép bạn để cung cấp cho tên những con số này trong chương trình của bạn. Trong trường hợp này, chiều cao tối đa của một kim tự tháp trong Mario đã 23, chứ không phải là đưa 23 trong mã của tôi chúng ta sẽ đề cập đến như cứng mã hóa 23 - thay vì điều này sẽ cho MAX_HEIGHT tên vào con số đó, để xuống đây trong vòng lặp do-trong khi của tôi bạn thực sự có thể tham khảo MAX_HEIGHT thay vì đặt số 23. [Sinh viên] lợi thế của việc đó là gì? Đó là một câu hỏi lớn. Một là khả năng đọc. Một lợi thế của việc sử dụng này # xác định là dễ đọc. Khi tôi đang đọc mã này, tôi có thể nhìn thấy những gì đang xảy ra. 

Tôi có thể thấy trong điều kiện này ở đây mà chúng tôi đang thử nghiệm cho chiều cao là <0, mà chúng ta có thể cũng được xác định là chiều cao tối thiểu hoặc chiều cao min. Một thuận lợi khác là tôi có thể đọc phần còn lại của dòng để xem rằng chúng ta cũng kiểm tra để đảm bảo rằng chiều cao không phải là lớn hơn chiều cao tối đa, bởi vì chúng tôi sẽ tiếp tục trong khi chiều cao lớn hơn chiều cao tối đa. Một thuận lợi khác là nếu tôi thu nhỏ một chút ở đây nếu tôi chạy chương trình này và tôi chạy nó, nói rằng, với 23 ngay bây giờ, nó sẽ in ra tất cả 23 hàng chỉ cần như thế. Nhưng nói tôi muốn thay đổi chiều cao tối đa, và bây giờ tôi muốn giới hạn chiều cao tối đa của kim tự tháp là chỉ nói người đàn ông, đó là sôi nổi. # Include, # xác định MAX_HEIGHT, và chúng ta hãy nói rằng chúng tôi muốn thiết lập nó bằng 10. Bây giờ, ở thời điểm này, tất cả những gì tôi phải làm là thay đổi nó trong một vị trí này. Tôi có thể biên dịch lại mã, và bây giờ nếu tôi cố gắng và gõ trong 12, nó sẽ nhắc tôi một lần nữa. Trong trường hợp này, chúng tôi chỉ sử dụng MAX_HEIGHT một lần. Nó không phải là lớn rắc rối một để đi và thay đổi nó trong vòng lặp trong khi nếu bạn cần. Tuy nhiên, trong các chương trình mà bạn đang tham khảo cùng một số lượng ma thuật hơn và hơn nữa, điều này # xác định cơ chế thực sự tiện dụng bởi vì bạn chỉ cần thay đổi một thời gian ở phía trên cùng của tập tin nó thường nơi bạn đặt chúng và sự thay đổi thấm qua phần còn lại của tập tin. 

Những thứ khác tôi muốn lưu ý trong nhiệm vụ này mà tôi nghĩ rằng trông thật sự tốt đẹp, một là đặt tên của các biến. Bạn thấy ở đây chúng ta đã có các biến số nguyên được gọi là hàng và được gọi là chiều cao. Spaces, băm, nó giúp làm cho mã dễ đọc hơn, làm cho nó một chút dễ hiểu hơn những gì đang thực sự xảy ra. Điều này là trái ngược với việc sử dụng, nói, chữ cái ngẫu nhiên hoặc chỉ gobbledygook hoàn toàn. Một điều cuối cùng tôi sẽ chỉ ra cho các vòng, thường những biến iterator, các quầy mà bạn sử dụng cho các vòng, nó là tiêu chuẩn và thông thường bắt đầu với một trong hai i và j và sau đó k và đi lên từ đó nếu bạn cần biến hơn, và điều này chỉ là một quy ước. Có rất nhiều các công ước. Nó phụ thuộc vào ngôn ngữ lập trình bạn đang sử dụng. Nhưng trong C, chúng tôi thường bắt đầu với tôi. Nó không làm cho cảm giác sử dụng, nói, a hoặc b tùy thuộc vào tình hình. Đó là một này. Nếu bây giờ bạn kéo lên phiên bản 2, bạn sẽ thấy một Mario, và điều này là tương tự như một trong những khác mà chúng ta chỉ nhìn thấy, nhưng nó không loại một cái gì đó mát mẻ. Nếu chúng ta nhìn vào phần này ngay tại đây bên trong bên trong vòng lặp for, họ đang sử dụng một số cú pháp tìm kiếm điên ở đây ngay trong dòng này. Điều này được gọi là một nhà điều hành ternary. Đó là một tuyên bố nếu người nào khác ngưng tụ thành một dòng. Điều kiện này là một phần trong dấu ngoặc đơn. Đó là tương đương với nói rằng nếu chiều cao <j - i - 1. Và sau đó các nội dung rằng nếu khối sẽ là không gian và sau đó các nội dung khác sẽ là # Nó cơ bản chỉ định một không gian để biến này. Nó đặt một không gian trong các nội dung của biến khối, nếu điều kiện này được đáp ứng, và nếu tình trạng này không được đáp ứng, sau đó biến khối được # Và sau đó, tất nhiên, thay vì xây dựng toàn bộ một chuỗi và in ra tất cả mọi thứ ở cuối giải pháp này in ra một ký tự tại một thời điểm. Khá mát mẻ. 

Một vài điều cần xem xét. Chúng tôi sẽ chuyển sang tham lam. Bây giờ nếu chúng ta nhìn vào tham lam, giải pháp đầu tiên này sử dụng các # định nghĩa khá một chút. Chúng tôi đã có một hằng số được xác định cho mỗi số khác nhau trong chương trình này. Chúng tôi đã có một cent cho mỗi đô la, một cho khu phố, dimes, nickels, và đồng xu, và bây giờ nếu chúng ta di chuyển xuống và đọc mã, chúng ta có thể thấy một do-while loop in tiêu chuẩn tất cả mọi thứ. Loại mấu chốt của vấn đề này đã nhận ra rằng bạn cần thiết để chuyển đổi các phao mà bạn đọc từ người sử dụng đến một số nguyên chính xác làm toán, và điều này là bởi vì với số dấu chấm động, giống như chúng ta đã nói trong bài giảng một thời gian ngắn, nó không chính xác có thể đại diện cho tất cả các giá trị duy nhất trên dòng số bởi vì có những giá trị vô hạn từ 3, 3,1 thậm chí. Bạn có thể có 3,01 và 3,001 và 3,0001, và bạn có thể tiếp tục đi. Nó chỉ ra bất cứ khi nào bạn đang làm việc bằng tiền, bạn thường muốn chuyển đổi nó sang định dạng số nguyên để bạn không mất đồng xu và các loại công cụ. Làm điều đó và làm tròn là chìa khóa. Giải pháp này sử dụng một thuật toán, hoàn toàn đơn giản tuyệt vời, giảm đi số lượng cent còn lại, lần đầu tiên theo quý, sau đó dimes, nickels, sau đó bằng đồng xu, và thêm vào số lượng tiền xu mỗi lần. 

Một giải pháp mà chúng ta sẽ thấy, như tôi phóng to và thu nhỏ đi để sửa đổi 4, đã có một khởi đầu rất giống nhau nhưng div thay vì sử dụng và mod ngay trên đây để tính toán số lượng cent. Này, số lượng các khu bằng số lượng xu chia cho 25, và lý do công trình này là bởi vì chúng tôi đang làm phân chia số nguyên, vì vậy nó loại bỏ bất kỳ còn lại. [Sinh viên] chúng tôi có nhận xét tìm kiếm? Nó thực sự phụ thuộc. [Sinh viên] Bạn cho ý kiến ​​nhiều hơn so với mã ngay tại đây. Yeah, và do đó, có một loạt các triết lý khác nhau về điều này. Triết lý cá nhân của tôi là mã của bạn thực sự là sự thật, giống như mã của bạn là những gì thực sự thực hiện trên máy tính, và do đó, mã của bạn nên được như có thể đọc được có thể không đòi hỏi phải như nhiều ý kiến. Điều đó nói rằng, khi bạn đang làm những điều mà là loại khó khăn toán học hoặc thuật toán, đó là tốt để nhận xét những người như vậy mà bạn có thể thêm thêm một chiều, thêm một lớp để bất cứ ai đang đọc mã của bạn. Trong các giải pháp này, thường họ được nhận xét nhiều hơn chỉ vì chúng tôi muốn để có thể phân phối chúng và có những người chọn chúng lên và đọc chúng khá dễ dàng. Nhưng chắc chắn, tôi sẽ đồng ý rằng đây là nặng. [Sinh viên] Nhưng khi nghi ngờ, đi nặng hơn? Khi nghi ngờ, đi nặng hơn. Một số người đôi khi sẽ nói 0 trả hoặc một cái gì đó như thế. Tôi nghĩ rằng đó là một nhận xét vô lý. Rõ ràng rằng những gì đang xảy ra. Tôi không cần tiếng Anh để nói với tôi rằng. Đôi khi người ta sẽ viết công cụ như "kthxbai!" Đó là loại dễ thương nhưng cũng không- đó không phải là sự khác biệt giữa các điểm bình luận hay không. Những loại ý kiến ​​chỉ ha, ha. Cool. 

Tại thời điểm này, chúng ta hãy bắt đầu làm việc trên các vấn đề Set 3 phần của câu hỏi. Nếu bạn kéo này lên một lần nữa, với tuần trước, chúng tôi sẽ không xem quần short trong phần này. Chúng tôi sẽ cho các bạn làm điều đó vào thời gian riêng của bạn và nói về những câu hỏi. Nhưng bây giờ trong phần này chúng ta sẽ dành thời gian nhiều hơn một chút nói về những điều cơ bản mã hóa như chúng tôi đã làm tuần trước, và thay vào đó, chúng ta sẽ tập trung hơn vào hơn một chút về lý thuyết, do đó, nói về tìm kiếm nhị phân và sau đó phân loại. Từ những người bạn của những người đã được sau đây cùng với các bài giảng, ai đó có thể cho tôi một bản tóm tắt về những gì là sự khác biệt giữa hệ nhị phân tìm kiếm và tìm kiếm tuyến tính? Chuyện gì đang xảy ra? Chắc chắn. Tìm kiếm tuyến tính tìm kiếm thông qua tất cả các phần tử trong danh sách được sắp xếp một của một của một của một, và tìm kiếm nhị phân chia danh sách thành 2 nhóm, kiểm tra nếu giá trị khóa mà bạn đang tìm kiếm lớn hơn hoặc ít hơn giá trị trung điểm mà bạn vừa tìm thấy, và nếu nó ít hơn, nó đi với danh sách thấp hơn và rồi chia đó một lần nữa, hiện các chức năng tương tự tất cả các con đường xuống cho đến khi nó tìm thấy điểm giữa để bằng với giá trị riêng của mình. Đúng. 

Tại sao chúng ta quan tâm? Tại sao chúng ta nói về việc tìm kiếm nhị phân so với tìm kiếm tuyến tính? Yeah. Nhị phân là nhanh hơn rất nhiều, vì vậy nếu bạn tăng gấp đôi kích thước của vấn đề phải mất thêm một bước chứ không phải là nhiều gấp đôi. Chính xác. Đó là một câu trả lời tuyệt vời. Tìm kiếm tuyến tính là rất nhiều kiểm tra một trong những yếu tố cùng một lúc, và như chúng ta đã thấy những ngày đầu tiên của bài giảng khi David đã đi qua ví dụ cuốn sách điện thoại của mình và tách ra một trang của cuốn sách điện thoại tại một thời điểm và tiếp tục làm điều đó hơn và hơn và hơn một lần nữa, nó sẽ đưa anh ta một thời gian rất dài để tìm thấy bất cứ ai trong sổ điện thoại, trừ khi, tất nhiên, ông đang tìm kiếm ai đó ở rất bắt đầu của bảng chữ cái. Với tìm kiếm nhị phân, bạn có thể đi nhanh hơn rất nhiều, và nó không phải chỉ hai lần là nhanh hay 3 lần là nhanh hay 4 lần nhanh. Nhưng vấn đề trở nên nhỏ hơn và nhỏ hơn và nhỏ hơn nhanh hơn nhiều. Để minh họa điều này, chúng tôi sẽ bắt đầu nói về những gì đang xảy ra khi chúng tôi viết tìm kiếm nhị phân. Vấn đề ở bàn tay là nếu tôi có một mảng của các số, nói, 1, 2, 3, 5, 7, 23, 45, 78, 12.323, và sau đó 9 với một tấn của số 0 sau nó, chúng tôi muốn để có thể để tìm ra thực sự nhanh chóng những gì có trong mảng của các số này. Tôi biết điều này có vẻ như ngớ ngẩn một chút và một chút contrived, bởi vì ngay bây giờ nó là. Chúng tôi có một mảng mà không có yếu tố rất nhiều trong nó, và nếu tôi yêu cầu một trong các bạn để tìm ra hay không 23 là trong mảng, bạn có thể làm điều đó khá nhanh chóng chỉ bằng cách liếc nhìn và nói với tôi rằng có hay không. Tương tự để xem xét là tưởng tượng nếu điều này là, nói, một bảng tính Excel với 10.000 hàng, 20.000 hàng. Tất nhiên, bạn có thể làm lệnh hoặc F F kiểm soát và tìm kiếm một cái gì đó lên. Bạn cũng có thể sử dụng các bộ lọc và các công cụ tìm kiếm, nhưng nếu bạn đã xem xét thông qua dòng tập tin bằng cách từng dòng, nó sẽ mất một thời gian dài để tìm thấy nó. Đó là loại giống như trong ví dụ cuốn sách điện thoại, quá, không ai nhìn qua trang một cuốn sách điện thoại tại một thời điểm. Thông thường, họ mở nó giữa, hoặc trong trường hợp của rất nhiều sách điện thoại và từ điển bạn thực sự đã keyed vào chữ cái đầu tiên, bạn lật lá thư đầu tiên và mở và bắt đầu đi qua đó. 

Nhắc nhở tôi về tên của bạn một lần nữa >> Sam. Sam. Như Sam nói, quá trình tìm kiếm tuyến tính là có được rất chậm, và thay vào đó với tìm kiếm nhị phân, cách công trình này là mỗi khi chúng tôi đi qua một sự lặp lại của thuật toán tìm kiếm của chúng tôi, chúng ta sẽ chia danh sách trong một nửa, về cơ bản, thành hai danh sách nhỏ hơn. Và sau đó lặp kế tiếp của vòng lặp, chúng ta sẽ phân chia lại một lần nữa vào các danh sách khác nhỏ hơn. Như bạn có thể thấy, vấn đề tiếp tục nhận được nhỏ hơn và nhỏ hơn bởi vì chúng tôi tiếp tục loại bỏ một nửa danh sách mỗi lần duy nhất. Làm thế nào để loại bỏ công việc? Cũng như một lời nhắc nhở, những gì chúng tôi đang đi để làm gì nếu chúng tôi là một máy tính và chúng tôi đã, nói, tìm kiếm số 5 trong danh sách này là chúng ta sẽ chọn một số ở giữa. Ở giữa của danh sách này, bởi vì có 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 số, chúng tôi muốn chọn số ở vị trí thứ 4 hoặc ở vị trí thứ 5, và chúng tôi gọi đó là giữa của danh sách của chúng tôi. Chọn số ở giữa. Sau đó, giống như Sam nói, chúng tôi sẽ kiểm tra để xem nếu con số đó là bằng số lượng mà chúng tôi muốn để có được hoặc số mong muốn của chúng tôi. Nếu đó là bằng nhau, sau đó chúng tôi đã tìm thấy nó. Chúng tôi giành chiến thắng. Nếu nó không bằng nhau, sau đó có một vài trường hợp. Hai trường hợp hoặc số lượng lớn hơn số lượng chúng tôi đang tìm kiếm tại, hoặc nó ít hơn. Nếu nó lớn, chúng tôi di chuyển về bên phải. Và nếu nó ít hơn, chúng tôi di chuyển sang bên trái. Và sau đó chúng tôi lặp lại toàn bộ quá trình một lần nữa trên một nửa hoặc nửa bên phải bên trái của danh sách. 

Vấn đề đầu tiên trong phần ngày nay là tìm hiểu làm thế nào chúng ta có thể thực sự bắt đầu để thể hiện điều này trong C code. Chúng tôi đã có giả ở đây. Những gì chúng tôi sẽ bắt đầu làm là tôi sẽ kéo lên không gian một thương hiệu mới, cứu sửa đổi này để chúng tôi có những ghi chú cho sau này, chúng tôi sẽ xóa tất cả những điều này, và sau đó sao chép và dán từ các thiết lập vấn đề thông tin này vào không gian của chúng tôi, và hy vọng điều này không phá vỡ. Hoàn hảo. Nếu bạn làm điều đó, sao chép và dán mã này vào không gian mới của bạn, vào một trống. Chúng ta hãy thử Daniel. Nếu bạn biên dịch và chạy chương trình này, nó hoạt động? Số >> nói gì vậy? Nó nói kiểm soát đạt đến kết thúc của chức năng không có khoảng trống. Yeah, vì vậy hãy để tôi thử chạy nó. Bạn đã nhìn thấy điều này trước khi? Bạn có biết điều này có nghĩa là gì? Được rồi, chúng ta hãy khảo sát tỉ mỉ một chút. Nó nói tại file.c on line 9, cột 1, chúng tôi có một lỗi, giống như bạn nói, và nó nói rằng nó bắt nguồn từ những cảnh báo lỗi và cảnh báo kiểu trả về. Nó trông giống như một cái gì đó đang xảy ra với kiểu trả về, có ý nghĩa. Chúng tôi đã có một chức năng không-không có giá trị, có nghĩa là chúng tôi đã có một chức năng mà không trả lại void. Một chức năng void là một trông như thế này: void foo (), và đó là khoảng trống vì kiểu trả về là void, có nghĩa là nếu chúng ta có một cái gì đó ở đây như trả lại 1, chúng tôi nhận được một lỗi trình biên dịch cho. Tuy nhiên, chúng tôi có một chức năng không trống. Không vô hiệu chức năng của chúng tôi trong trường hợp này là chức năng tìm kiếm của chúng tôi bởi vì nó có một kiểu trả về của bool. Khi nó nói rằng kiểm soát đạt đến kết thúc của một hàm không có giá trị không, đó là bởi vì tìm kiếm không có một tuyên bố trở lại. Nó không trả lại bất cứ điều gì của bool loại. 

Chúng ta có thể khắc phục điều đó, và bạn nghĩ gì tìm kiếm phải trả lại theo mặc định? Điều gì cần được trả lại mặc định giá trị của tìm kiếm? Bởi vì đó là những gì chúng ta có thể đặt ở cuối. Charlotte, làm bạn có bất kỳ? Đúng hay sai >> Đúng hay sai? Mà một trong những? False. Tôi không biết. False? Hãy thử lại nó. Tại sao bạn sẽ nói return false? Đó là trực giác tuyệt vời. Charlotte] Tôi không biết. Chúng tôi sẽ quay trở lại sai trong trường hợp này vì điều này sẽ được mặc định của chúng tôi nếu vì một lý do nào đó trong danh sách là rỗng hoặc kim mà chúng tôi đang tìm kiếm không tồn tại. Sau đó, vào cuối, nếu chúng ta không trở lại đúng sự thật trước đó trong chức năng này, chúng tôi luôn luôn biết rằng chức năng này sẽ nói nope, nó không có trong mảng. Nó không phải trong đống cỏ. Bây giờ nếu chúng tôi biên dịch và chạy nó cho tôi lưu này, vì vậy chúng ta có thể kéo nó lên. Bây giờ nếu chúng ta biên dịch và chạy chương trình của chúng tôi, nó được xây dựng. Chúng tôi nhận được dấu nhắc nhỏ của chúng tôi. Nếu tôi nhấn 4-uh-oh. Nó không in ra bất cứ điều gì. Có vẻ như tất cả mọi thứ đã kết thúc không sao. Chúng tôi đã có để điền vào. Chúng tôi nói về thuật toán trong giả một chút trước. Hãy cho tôi thấy, tiết kiệm, và tôi sẽ kéo mà thuật toán trở lại một lần nữa. Hãy đánh anh chàng này. Nope. Có nó được. Làm thế nào để chúng ta làm điều này? Điều gì sẽ là một chiến lược tốt để bắt đầu mã này? Bạn phải chọn một số ở giữa. Làm thế nào để chúng ta chọn một số ở giữa của một mảng? Bất cứ lời đề nghị? [Sinh viên] strlen chia cho 2. Strlen chia cho 2. Đó là một tuyệt vời. Strlen công trình với các loại đặc biệt của mảng. Những mảng? Chuỗi mảng, mảng ký tự. Nó là cùng một loại khái niệm mà chúng ta muốn áp dụng, nhưng chúng ta không thể sử dụng strlen vì chúng ta không có một mảng các ký tự. Chúng tôi có một mảng ints. Nhưng strlen không nhận được gì cho chúng ta? Bạn có biết những gì nó được cho chúng ta? [Sinh viên] strlen chúng ta có được chiều dài. Chính xác, chúng ta có được chiều dài. Strlen được chiều dài của mảng cho chúng tôi. 

Làm thế nào để chúng ta nhận được rằng trong chương trình tìm kiếm nhị phân của chúng tôi? Làm thế nào bạn sẽ nhận được chiều dài của một mảng? [Sinh viên] strlen? Bạn có thể có được chiều dài của một mảng chuỗi định dạng đúng C với strlen. , Tuy nhiên, vấn đề là chúng ta không có một mảng chuỗi. Nếu chúng ta nhìn lại đoạn mã này, chúng tôi có mảng số nguyên này. Làm thế nào để chúng ta biết bao lâu nó? [Sinh viên] Có một tương đương cho thiết bị đầu cuối, như l int hoặc một cái gì đó? Nó chỉ ra có thực sự không phải là, và như vậy trong một cách, đây là một trong những điều đó là tốt để biết về C, rằng không có cách nào để có được chiều dài của một mảng nếu tất cả những gì tôi cung cấp cho bạn là mảng. Lý do nó hoạt động với chuỗi, lý do strlen công trình, là bởi vì nếu một chuỗi được định dạng, nó sẽ có đó đặc biệt \ 0 ký tự ở cuối. 

Bạn cũng có thể tưởng tượng nếu bạn có một chuỗi không đúng định dạng và không có \ 0 ký tự có, sau đó toàn bộ điều không làm việc. [Sinh viên] Bạn có thể thêm \ 0? Chúng ta có thể trong trường hợp này. Chúng ta có thể thêm một số loại \ 0 hoặc một số loại biểu nhân vật và sau đó sử dụng. Nhưng đó là không hoàn toàn đi làm việc bởi vì 0 \ cho một loại char, và ở đây chúng tôi đã có ints. Điều khác là nếu chúng ta sử dụng một giá trị đặc biệt như -1 để đánh dấu sự kết thúc của một mảng sau đó chúng tôi không bao giờ có thể lưu trữ một -1 trong mảng số nguyên của chúng tôi. Chúng tôi bị mắc kẹt. Nó chỉ ra rằng cách duy nhất để có được chiều dài của một mảng trong C là để thực sự nhớ nó khi bạn cài đặt nó và sau đó vượt qua nó xung quanh với mảng để bất cứ khi nào tôi có một chức năng mà sẽ làm một số công việc trên một mảng số nguyên hoặc nổi hoặc tăng gấp đôi hoặc những gì có bạn, Tôi cũng cần phải cung cấp cho các chức năng chiều dài của mảng, và đó là chính xác những gì chúng tôi đã thực hiện ở đây trong chức năng tìm kiếm. Nếu bạn nhìn, những gì chúng tôi đã làm khi chúng ta vượt qua trong mảng của chúng tôi ở đây, chúng tôi cũng vượt qua trong chiều dài, kích thước. Nó chỉ xảy ra mà chúng tôi đã được gọi là biến này ở đây, tham số này hoặc đối số. Điều này được gọi là danh sách đối số của một chức năng hoặc danh sách tham số, và còn được gọi là đối số hoặc các thông số. Số người sử dụng thuật ngữ khác nhau tại các thời điểm khác nhau. Tôi đôi khi trao đổi bản thân mình. Nó chỉ như vậy sẽ xảy ra rằng biến này ở đây được đặt tên tương tự này # xác định ở đây. Nhưng chúng không phải là điều tương tự. Vốn không thành vấn đề. 

Nếu bạn nhìn vào những gì xảy ra ở đây, chúng ta khai báo mảng int của chúng tôi, mà chúng tôi đã gọi là số. Chúng tôi đã cho nó kích thước của chúng tôi, tương ứng của chúng tôi # xác định ở đầu trang. Nó sẽ là 8. Và sau đó khi chúng tôi sau đó gọi chức năng tìm kiếm của chúng tôi dưới đây, chúng tôi vượt qua trong số chúng ta muốn tìm kiếm, mà chúng tôi đã nhắc nhở, nhận được từ người sử dụng. Chúng tôi vượt qua trong mảng, con số này, và sau đó chúng tôi cũng có để vượt qua trong kích thước của mảng, và sau đó được lưu trữ giá trị của kích thước 8 hoặc thông qua kích thước này số nguyên được gọi là biến. Chúng tôi có các kích thước của mảng. Bây giờ nếu chúng ta trở lại những gì chúng ta đã nói về trước đó, Tôi nghĩ rằng Missy đưa ra quan điểm rằng những gì chúng tôi cần làm là có được chiều dài của mảng và chia nó cho 2, và sẽ cung cấp cho chúng tôi là trung điểm. Hãy xem. Tôi có thể có ai đó viết này và lưu nó trong không gian của họ? Làm thế nào về Leila? Tôi có thể có bạn viết điều này trong? Viết những dòng đầu tiên, nơi bạn có chiều dài của mảng và trung điểm và lưu nó trong một biến mới. Tôi sẽ cung cấp cho bạn một vài giây. Bạn đã sẵn sàng? [Sinh viên không nghe được] Chắc chắn, tôi có thể tính toán trung điểm của mảng haystack bên trong chức năng tìm kiếm sử dụng chiều dài của mảng haystack, đó là biến kích thước? Không có gì khó ở đây. [Leila] kích thước / 2 và chỉ Và lưu nó, và nhấn nút Save ở đây ở đầu trang, và chúng tôi sẽ kéo nó lên. Hoàn hảo. Hiện chúng tôi đi. Awesome. 

Như là, điều này sẽ biên dịch? [Leila] Không, nó cần cao hơn. [Nate] Yeah, vì vậy những gì chúng ta cần phải làm gì? [Leila] Cũng giống như điểm giữa int hoặc một cái gì đó. Awesome. Yeah, chúng ta hãy làm điều đó, int trung điểm = kích thước. Điều này sẽ biên dịch? Hãy xóa bình luận này và làm cho nó ra khỏi con đường. Điều gì sẽ không biên dịch về điều này? Chúng tôi sẽ không làm bất cứ điều gì với số nguyên, vì vậy chúng ta cần phải in nó hoặc một cái gì đó như thế. Yeah, chính xác. Chúng tôi sẽ nhận được một biến không sử dụng. Những gì người khác không phải là đi làm việc về điều này? Tôi nghĩ rằng bạn nói điều gì đó, Sam. Dấu chấm phẩy. Yeah, tôi là thiếu những dấu chấm phẩy. Nó sẽ là một điều không đổi trong suốt quá trình của thuật ngữ này. Điều cuối cùng tôi sẽ làm là tôi sẽ đưa một số không gian màu trắng hai bên của nhà điều hành này ở đây, vì đó là thường làm thế nào chúng ta làm điều đó theo hướng dẫn phong cách của chúng tôi. Chúng tôi đã có trung điểm của mảng của chúng tôi. Bây giờ nếu chúng ta nhớ lại thuật toán của chúng tôi, bước thứ hai mà chúng tôi phải làm khi chúng tôi có trung điểm là gì? [Sinh viên] Nếu nó lớn không nghe được. Yeah, vì vậy chúng ta phải làm một số loại so sánh, và chúng tôi đang so sánh những gì ở đây? Bạn nói rằng nếu nó lớn hơn. Trong câu đó đề cập đến là gì? Số lượng mà đi lên, nếu đó là lớn hơn so với trung điểm, sau đó đi đến mảng? Chính xác, do đó, số lượng mà đi lên khi chúng ta- Kim, vì vậy chúng tôi đang so sánh kim, và chúng tôi đang so sánh với kim? Bởi vì kim là những gì chúng tôi đang tìm kiếm. Chúng tôi đang so sánh nó để có được trung điểm. 

Nhưng nó có ý nghĩa để kiểm tra xem nếu kim = điểm giữa? Điều đó làm cho tinh thần? Không ai không đồng ý? Hãy cung cấp cho nó một thử, nếu (kim == trung điểm). [Sinh viên] printf bạn thấy nó. [Nate] printf ("Chúng tôi đã tìm thấy nó \ n"); Nếu không - Tôi sẽ bắt đầu làm một cái gì đó khác nhau ở đây. Tôi sẽ bắt đầu đặt niềng răng xung quanh nếu báo cáo tất cả các thời gian chỉ bởi vì nếu chúng ta thêm nhiều công cụ, sau đó chúng tôi không nhận được các trình biên dịch. Yeah, Sam. Bạn đã có một điểm. Vấn đề là trung điểm đại diện cho một vị trí trong mảng, nhưng bạn có thể có được nó để đại diện cho giá trị ở vị trí đó của mảng. Đó là một điểm tuyệt vời. Có phải tất cả mọi người nghe những gì Sam nói? Ông cho biết trung điểm đó như là chỉ đại diện cho một vị trí trong mảng, nhưng nó không phải là yếu tố thực tế trong mảng. Nếu bạn nghĩ về các mã như được viết ngay bây giờ, nếu chúng ta nhìn vào mảng này xuống đây, trong đó có 8 yếu tố trong nó, giá trị của điểm giữa để được chức năng này là gì? [Sinh viên] 4. [Nate] 4. Nếu chúng ta nhìn cho số 4 - và chúng tôi chỉ có thể chạy mã này và đặt một khuôn mặt nhỏ bé đáng buồn ở đây bởi vì chúng tôi đã không tìm thấy nó nếu chúng ta chạy mã này như là ngay bây giờ, tải lên nó, xây dựng, cho phép tôi di chuyển xuống, và nếu chúng ta nhìn cho số 4, chúng tôi tìm thấy nó, nhưng chúng tôi đã không có được điều này printf có. Một lý do là chúng tôi đã không trở lại đúng sự thật, nhưng chúng tôi đã thực sự tìm thấy số 4? Và Sam nói không. Chúng tôi đã tìm được gì? Chúng tôi thực sự tìm thấy điểm giữa, mà nếu chúng ta nhìn vào mảng xuống đây, nó sẽ là phần tử tại chỉ số 4 mà chúng tôi đang tìm kiếm, là 23. 

Làm thế nào để chúng ta thực sự có được yếu tố đó tại trung điểm và không chỉ là trung điểm riêng của mình? [Sinh viên] Chúng tôi sẽ nhập char hoặc một cái gì đó? Điều gì sẽ làm, chỉ vì tò mò? Bạn có thể xây dựng thêm một chút? Bạn có để biến đổi các vị trí vào số lượng, vì vậy bạn đã có để làm cho một số kết nối Tôi nghĩ rằng đó là char, nhưng nó có thể không. Vâng, đó là một điểm tốt. Chúng tôi đã làm rất nhiều này vị trí chuyển đổi thành các ký tự, các ký tự, trong hai bộ vấn đề đầu tiên. Nó chỉ ra rằng ở đây, điều này là gần như tương tự truy cập các ký tự thứ i trong một chuỗi, nếu có ý nghĩa. Ở đây chúng tôi muốn truy cập vào các phần tử trung điểm. Làm thế nào để chúng ta làm điều đó? Kevin, làm bạn có bất cứ lời đề nghị làm thế nào chúng ta có thể làm điều đó? Bạn có thể làm haystack, mở khung, giữa, đóng khung. Bạn có thể viết cho chúng ta? Lưu nó ở đây, và chúng tôi sẽ kéo mà lên. Chúng tôi đang tìm kiếm ở dòng 9, và chúng tôi nhận ra rằng chúng tôi không muốn so sánh kim vào trung điểm, nhưng thay vào đó, chúng tôi muốn so sánh kim các yếu tố ở điểm giữa vị trí trong mảng haystack của chúng tôi. Cool. Hiện chúng tôi đi. Yeah, trông khá tốt, nếu (kim == haystack [trung điểm]). Chúng tôi đã tìm thấy nó. Bây giờ nếu chúng ta chạy lại mã we'll lên một chút-bit nó biên dịch, nó chạy, và bây giờ nếu chúng ta nhìn cho 4, chúng tôi đã không tìm thấy nó bởi vì bây giờ chúng tôi đang thực sự nhận số 23. Chúng tôi đang nhận được giá trị 23, và đó là những gì chúng ta đang so với kim của chúng tôi. Nhưng đó là tốt. Đó là một bước đi đúng hướng. 

Đó là những gì chúng tôi đang cố gắng làm. Chúng tôi không cố gắng để so sánh kim so với các vị trí trong mảng mà là chống lại các yếu tố thực tế trong mảng. Nếu chúng ta nhìn lại một lần nữa tại bước tiếp theo trong thuật toán của chúng tôi, bước tiếp theo là gì? Leila đã đề cập đến nó một thời gian ngắn. [Sinh viên] Kiểm tra xem nếu nó lớn hơn hoặc nhỏ hơn và sau đó quyết định cách để di chuyển. [Nate] Yeah, vậy làm thế nào chúng tôi sẽ làm điều đó? Bạn có thể đặt trong một số-sẽ tiết kiệm này sửa đổi, và sau đó nếu bạn đặt trong một số ngành, nghề sẽ làm điều đó. Yeah, Charlotte >> Tôi có một câu hỏi. Nên nó không được trung điểm - 1 bởi vì điều đầu tiên là nó là 0 lập chỉ mục, vì vậy nếu chúng ta đặt 4, đó không phải là thực sự là nhân vật chúng tôi đang tìm kiếm? Có, và các vấn đề khác với đó là- đó là một nắm bắt tuyệt vời, bởi vì những gì sẽ xảy ra có thể nếu chúng ta tiếp tục di chuyển và chúng tôi không bao giờ điều chỉnh ban đầu? Tôi đoán những gì chúng ta có thể kết thúc làm là cố gắng để truy cập các yếu tố ở vị trí thứ 8 của mảng, trong trường hợp này không tồn tại. Chúng tôi sẽ muốn làm một số loại kế toán thực tế rằng chúng ta có một số chỉ mục zero. Charlotte] Xin lỗi, tôi có nghĩa là trung điểm - 1 trong dấu ngoặc vuông. Chúng ta có thể làm điều đó. Chúng tôi sẽ trở lại vấn đề này chỉ là một chút. Khi chúng tôi bắt đầu để có được đến vòng lặp thực tế, đó là khi chúng ta thực sự sẽ thấy điều này đi vào chơi. Trong thời gian này, chúng ta có thể làm điều này, nhưng bạn hoàn toàn đúng. Đó không lập chỉ mục sẽ có một hiệu ứng mà chúng ta cần phải chiếm. Hãy xem. 

Làm thế nào là lớn hơn, nhỏ hơn? [Sinh viên] làm thế nào để làm các việc lớn hơn, nhỏ hơn một phần. Tôi chỉ không chắc chắn những gì để in nếu bạn thấy rằng nó là ít hơn điểm giữa đống cỏ khô hoặc lớn hơn. Ở đây tôi có thể tiết kiệm những gì I've- [Nate] Yeah, nếu bạn lưu những gì bạn đã có, và chúng tôi sẽ kéo nó lên. Hiện chúng tôi đi. [Sinh viên] Và tôi đặt dấu hỏi cho những gì tôi không biết. [Nate] sẽ rất tốt. Ở đây chúng tôi đã có dấu hỏi bởi vì chúng tôi vẫn không biết những gì chúng ta sẽ khá làm. Những gì chúng tôi muốn làm oops, chúng tôi đã có một số dấu ngoặc tất cả các funky trên chúng ta. Chúng tôi sẽ sửa chữa những niềng răng. Hiện chúng tôi đi. Và vì vậy chúng tôi làm những gì muốn làm, theo thuật toán của chúng tôi, nếu chúng ta không tìm thấy kim? Nói rằng trong trường hợp cho kim là ít hơn so với những gì chúng tôi đang tìm kiếm. Kevin. Chỉ nhìn vào nửa bên trái. Đúng, vì vậy chúng tôi sẽ đặt một bình luận ở đây nói rằng "hãy nhìn vào nửa bên trái". Và nếu kim lớn hơn haystack tại trung điểm, chúng tôi những gì bạn muốn làm gì? [Sinh viên] Sau đó bạn nhìn vào nửa bên phải. Nhìn vào nửa bên phải, nhìn vào đúng một nửa. " Không quá tồi tàn. Được rồi, vì vậy tại thời điểm này, mọi thứ đang tìm kiếm khá tốt. Các vấn đề với mã như bằng văn bản là gì? [Sinh viên] Bạn không có thiết bị đầu cuối cho nửa. Phải, chúng tôi không có thiết bị đầu cuối cho nửa. Chúng tôi cũng chỉ sẽ phải đi qua điều này một lần. Chúng tôi sẽ chỉ nhìn tại một trung điểm. Một trong hai yếu tố là có, hoặc nó không phải. Để hoàn thành điều này, chúng tôi sẽ cần phải làm một số loại của sự lặp lại. Chúng tôi cần phải tiếp tục lặp đi lặp lại cho đến khi chúng tôi tìm thấy rằng một trong hai yếu tố là ở đó bởi vì chúng tôi đã thu hẹp xuống và cuối cùng đã tìm thấy nó, hoặc nó không ở trong đó bởi vì chúng tôi đã xem xét thông qua tất cả những điều trong nửa thích hợp của mảng và thấy rằng không có gì là ở đó. 

Bất cứ khi nào chúng tôi đã nhận sự lặp lại xảy ra, chúng tôi sẽ sử dụng những gì? [Sinh Viên] Một vòng lặp. Một số loại vòng lặp. Vâng. [Sinh viên] Chúng ta có thể làm một vòng lặp do-trong khi và có nó làm điều đó và sau đó trong khi kim, không có gì không bằng tôi không chắc chắn nơi tôi đã đi với điều đó. Tuy nhiên, loại giống như làm điều đó miễn là nó không bằng giá trị mà người dùng nhập vào. Yeah, vì vậy chúng ta hãy xem, cách này có thể viết riêng của mình? Bạn hãy sử dụng một vòng lặp do-trong khi. Trường hợp không làm bắt đầu? [Sinh viên] Ngay sau khi kích thước / 2. [Nate] Được rồi, và chúng tôi sẽ làm gì? Chúng tôi sẽ điền vào trong khi sau đó. Chúng tôi sẽ làm gì? [Sinh viên không phải chúng tôi muốn làm tất cả những thứ chúng tôi có trong phần nếu [Nate] tất cả các công cụ này, tuyệt vời. Sao chép và dán. Ồ, người đàn ông. Hãy xem, nếu công trình này, nếu chúng ta có thể tab này hơn. Beautiful. Được rồi, và chúng tôi tiết kiệm này, do đó bạn có nó. Được rồi, và chúng tôi sẽ để làm điều này trong khi điều kiện trong khi bạn đang theo đuổi là gì? [Sinh viên] Trong khi kim không bằng, do đó, như dấu chấm than. Nhưng tôi không chắc chắn chính xác những gì mà chưa. [Nate] Yeah, đây là một cách để làm điều đó. Sam, để bạn có một bình luận? [Sam] Tôi nhớ khi tôi nhìn vào các đoạn video, Tôi lấy một ảnh chụp màn hình của một của giống như khi chúng ta đã làm giả cho nó, đã có một số mối quan hệ giữa max và min. Tôi nghĩ đó là một cái gì đó như thế nếu tối đa là bao giờ ít hơn min. Đã nhận nó. [Sam] Hoặc như nếu tối đa là không ít hơn phút hoặc một cái gì đó như thế, bởi vì điều đó có nghĩa là bạn đã tìm kiếm tất cả mọi thứ. 

Yeah, vì vậy những gì âm thanh như max và min đang đề cập đến? [Sam] Giá trị mà số nguyên sẽ thay đổi liên quan đến nơi mà chúng tôi đặt tại điểm giữa. Chính xác. [Sam] Vào thời điểm đó, nó đi [không nghe được tính max và min. Trung điểm là ý tưởng này max và min. Đó có ý nghĩa nhằm giúp mọi người? Nếu chúng ta bắt đầu tìm kiếm như thế nào chúng tôi sẽ làm điều này lặp đi lặp lại, bạn hoàn toàn đúng mà chúng ta muốn sử dụng một số loại làm trong khi vòng lặp. Nhưng tôi nghĩ nếu chúng ta nhớ những gì đang xảy ra tại vị trí của mảng này và những gì đang thực sự xảy ra - Tôi sẽ viết ở đây tại lặp đi lặp lại đầu tiên của tìm kiếm nhị phân, chúng tôi có Tôi sẽ sử dụng b và e để biểu thị sự bắt đầu. Và sau đó là kết thúc của mảng của chúng tôi. Chúng tôi biết rằng bắt đầu từ lúc 4 quyền ở đây, và chúng ta biết rằng cuối cùng là 108. Nói rằng chúng tôi đang tìm kiếm cho số 15. Lần đầu tiên chúng tôi làm điều này, như chúng ta đã thấy, trung điểm là hoặc sẽ là 16 hoặc 23 tùy thuộc vào cách chúng tôi tính toán những điều trên. Kể từ khi đồng đều chia ở giữa sẽ cung cấp cho chúng tôi không gian này giữa 16 và 23, chúng ta có thể không đồng đều chia hoặc chia và nhận được tại một trung điểm thật sự. Chúng tôi sẽ xem xét ở mức 16. Chúng tôi sẽ nhận ra "Hey, 16> 15 mà chúng tôi đang tìm kiếm." Để sau đó nhìn vào nửa bên trái của mảng những gì chúng ta sẽ kết thúc làm là loại bỏ toàn bộ trên phần này và nói: "Được rồi, bây giờ thiết bị đầu cuối của chúng tôi sẽ được ở đây." Phiên bản kế tiếp của vòng lặp của chúng tôi, chúng tôi bây giờ nhìn vào mảng này, hiệu quả đã bị loại bỏ phần này bởi vì bây giờ nếu chúng ta lấy trung điểm là sự khác biệt giữa đầu và kết thúc, chúng ta thấy trung điểm của chúng tôi là 8, mà sau đó chúng tôi có thể kiểm tra 8 để xem nơi nó liên quan đến số lượng chúng tôi đang tìm kiếm, 15, tìm thấy rằng 15 là lớn hơn, vì vậy chúng ta phải di chuyển đến phần bên phải của danh sách, mà chúng ta biết vì chúng ta là con người, và chúng ta có thể nhìn thấy nó. Chúng ta biết rằng phần bên phải sẽ là nơi chúng tôi tìm thấy nó, nhưng máy tính không biết điều đó, vì vậy những gì chúng tôi sẽ làm là chúng tôi sẽ thực sự có này đi lên, và bây giờ bắt đầu và kết thúc cùng một chỗ, để trở thành trung điểm số duy nhất trong danh sách tại thời điểm đó, mà là 15, và chúng tôi đã tìm thấy nó. Điều đó sáng tỏ một số nơi này tối đa toàn bộ và ký hiệu min sẽ, theo dõi của các thiết bị đầu cuối của mảng để tìm ra làm thế nào để thu hẹp xuống? 

Điều gì sẽ xảy ra nếu điều này là không bằng 15? Nếu chúng ta đang tìm kiếm 15 và thay vào đó, con số này cũng là 16? Chúng tôi muốn nói, "Ồ, nó lớn. Chúng tôi muốn quay trở lại bên trái ". Và chúng ta sẽ di chuyển điện tử của chúng tôi sang bên phải, điểm mà tại đó chúng ta có một thiết bị đầu cuối mà có thể xung đột. Nó sẽ không thể tìm kiếm cho các yếu tố nữa bởi vì bây giờ chúng tôi có thiết bị đầu cuối của chúng tôi và điểm bắt đầu của chúng tôi, max và min của chúng tôi của chúng tôi, hiện nay lộn. Chúng tôi tìm kiếm thông qua toàn bộ mảng. Chúng ta không thể tìm thấy bất cứ điều gì. Đó là điểm mà tại đó, chúng tôi muốn nói, "Được rồi, chúng ta sẽ dừng thuật toán này. Chúng tôi không tìm thấy bất cứ điều gì. Chúng tôi biết nó không phải ở đây. " Làm thế nào là se đi đâu? [Sinh viên] Làm thế nào chính xác là máy tính chuyển đổi cuối cùng? Làm thế nào để cuối cùng kết thúc trước khi bắt đầu? Cuối cùng kết thúc trước khi bắt đầu vì môn toán mà chúng ta sẽ làm mỗi khi chúng ta làm điều này. Cách chúng ta trao đổi là nếu bạn nhìn vào lần đầu tiên chúng tôi làm điều này trao đổi nơi mà chúng tôi có sự khởi đầu tại 4 và kết thúc tất cả các con đường xuống tại 108 và trung điểm của chúng tôi, nói rằng, ở tuổi 16 - Tôi sẽ thiết lập lại điều này trở lại 15-nếu chúng ta đang tìm kiếm cho 15, chúng tôi biết rằng những gì chúng ta đã làm khi chúng tôi kiểm tra số 16 và thấy rằng nó là lớn hơn và muốn loại bỏ toàn bộ phần bên phải của danh sách, chúng ta đã thấy rằng những gì chúng tôi muốn làm di chuyển điện tử này ngay tại đây. Hiệu quả, e đã chuyển một trước khi trung điểm. Tương tự như vậy, khi chúng tôi đã làm điều này lặp đi lặp lại của thuật toán và trung điểm lên 8, chúng tôi thấy rằng 8 <15, vì vậy chúng tôi muốn di chuyển b 1 qua trung điểm. Bây giờ, bắt đầu và kết thúc là cả hai cùng nhau này 15. 

Nếu chúng ta đã xảy ra để tìm kiếm một số giá trị khác, chứ không phải 15, hoặc nếu 15 này đã thay vào đó là một 16, chúng ta sẽ thấy rằng điện tử, chúng tôi muốn di chuyển một trước khi trung điểm. Bây giờ e sẽ ở đó lộn ít hơn b. Hãy đi bộ thông qua làm thế nào chúng ta thực sự kết thúc mã hóa thuật toán này. Chúng ta biết rằng chúng ta muốn có tính toán này trung điểm. Chúng ta cũng biết rằng chúng ta muốn theo dõi các đầu và cuối của mảng của mảng hiện tại của chúng tôi vì vậy chúng tôi có thể tìm ra nửa bên trái của danh sách này và nửa bên phải của danh sách là. Chúng tôi làm điều đó với một trong hai bắt đầu và kết thúc, hoặc chúng ta có thể gọi họ là min và max. Tôi sẽ sử dụng bắt đầu và kết thúc thời gian này. Khi chúng ta bắt đầu, nếu chúng ta nhìn lại ví dụ của chúng ta ở đây, đầu của chúng tôi đã được thiết lập để bắt đầu của mảng, tự nhiên. Những gì chỉ số này? Những gì chúng ta nên bắt đầu được? Daniel. [Daniel] Haystack [0]. [Nate] Yeah, vì vậy chúng tôi có thể thiết lập nó bằng haystack [0]. , Tuy nhiên, vấn đề là điều này cho chúng ta không phải là vị trí của các yếu tố đầu tiên. Nó cho chúng ta các chỉ số của phần tử đầu tiên hoặc giá trị thực tế rằng vị trí đầu tiên. [Sinh viên] sẽ chuyển đổi tới 0,20? [Nate] Điều gì sẽ làm được-tốt, nó sẽ không làm bất kỳ chuyển đổi nhanh. Những gì nó sẽ làm là nó sẽ lưu trữ một 4 trong bắt đầu, và sau đó nó sẽ được khó khăn để so sánh chống lại bắt đầu bởi vì bắt đầu sẽ được giữ giá trị là 4, đó là sự khởi đầu của mảng của chúng tôi, nhưng chúng tôi muốn theo dõi các chỉ số trong mảng như trái ngược với các giá trị. Chúng tôi thực sự sẽ sử dụng một 0, như thế. Để kết thúc của mảng-Charlotte đưa lên sớm hơn một chút. Đây là nơi mà chúng tôi sẽ đưa vào tài khoản các chỉ mục không. 

Charlotte, cuối mảng là những gì? Chỉ số cuối cùng là gì? [Charlotte] Size - 1. Yeah, và có kích thước chúng tôi nên sử dụng? Chúng ta có nên sử dụng kích thước vốn hoặc kích cỡ chữ thường? Vốn kích thước. Trong trường hợp này, chúng ta có thể sử dụng kích thước vốn. Nếu chúng ta muốn chức năng này để được cầm tay và sử dụng chức năng này trong các chương trình khác, chúng tôi thực sự có thể sử dụng kích thước chữ thường. Thật là tốt quá. Nhưng Charlotte là hoàn toàn đúng mà chúng ta muốn có kích thước - 1. Tại điểm [Sinh viên] Làm thế nào mà bạn có thể sử dụng kích thước chữ hoa? Làm thế nào mà chúng ta có thể sử dụng kích thước chữ hoa? Nó chỉ ra rằng những # định nghĩa thực sự, dưới mui xe, một văn bản như tìm kiếm và thay thế, nếu có ý nghĩa. Khi bạn biên dịch mã của bạn, giai đoạn tiền xử lý của trình biên dịch đi qua các tập tin, và có vẻ ở khắp mọi nơi mà bạn đã viết quy mô vốn, và nó thay thế văn bản đó theo nghĩa đen với một 8, chỉ như thế. Trong ý nghĩa đó, điều này là rất khác nhau từ một biến. Nó không mất bất kỳ không gian trong bộ nhớ. Đó là một thủ thuật thay thế văn bản đơn giản. Trong trường hợp này, chúng ta sẽ sử dụng kích thước. Từ đây, chúng tôi muốn làm một số loại của sự lặp lại, và chúng tôi đang đi đúng hướng với vòng lặp do-trong khi của chúng tôi. Chúng tôi muốn làm một cái gì đó cho đến khi một điều kiện không giữ nữa, và như chúng ta đã thấy ở trên, chúng tôi thấy rằng tình trạng thật sự mà chúng ta không muốn kết thúc là ít hơn so với bắt đầu. 

Đây là điều kiện của chúng tôi dừng lại. Nếu điều này xảy ra, chúng tôi muốn dừng lại và tuyên bố như thế, "Này, chúng tôi đã không tìm thấy bất cứ điều gì." Để thể hiện điều này, chúng tôi muốn sử dụng một số loại vòng. Trong trường hợp này, nó sẽ là một vòng lặp do-while, vòng lặp for, vòng lặp trong khi? Chúng tôi có một vòng lặp do-trong khi ở đây. Bạn có những người như cách tiếp cận đó? Bạn có nghĩ rằng chúng ta nên cố gắng một cách tiếp cận khác nhau? Kevin, bất kỳ suy nghĩ? Chúng ta có thể có một vòng lặp trong khi vì chúng ta biết tối đa sẽ lớn hơn min anyways bắt đầu. Yeah, vì vậy không có khởi tạo cần phải xảy ra. Những vòng lặp do-while là tuyệt vời khi bạn phải khởi tạo một cái gì đó trước khi sau đó kiểm tra, trong khi đó đây chúng ta biết rằng chúng tôi sẽ không để giữ reinitializing cả hai bắt đầu và kết thúc mỗi vòng của vòng lặp. Chúng ta biết rằng chúng ta muốn khởi tạo cho họ, sau đó kiểm tra điều kiện của chúng tôi. Trong trường hợp này, tôi thực sự sẽ đi với một vòng lặp trong khi đơn giản. Nó chỉ ra rằng vòng lặp do-while được sử dụng khá thường xuyên. Rất nhiều nơi thậm chí không dạy làm trong khi các vòng. Họ đang tốt để xử lý đầu vào của người dùng, vì vậy chúng tôi đã nhìn thấy rất nhiều người trong số họ cho đến nay. Nhưng bình thường, trong khi vòng lặp là rất phổ biến hơn. Nó chỉ ra rằng tình trạng này là bằng văn bản sẽ không thực sự làm cho chúng tôi nhiều tốt, và tại sao vậy? Tôi xin lỗi, tôi không biết tên của bạn. Tôi Jerry. >> Xin lỗi? Đó là B-O-R-U-I. Oh, okay. Tôi không nhìn thấy bạn trên danh sách của tôi. Oh, đó là bởi vì-oh, có ý nghĩa. Bạn có một ý tưởng về lý do tại sao điều này vòng lặp trong khi không có thể làm việc như dự định, như bằng văn bản với điều kiện? [Jerry] Bạn có nghĩa là như bạn muốn tất cả những thứ sau khi nó vào? Yeah, vì vậy đó là một. Chúng tôi có thể phải đặt tất cả các công cụ này vào vòng lặp trong khi, đó là hoàn toàn đúng sự thật. Một thứ khác mà là nhiều hơn một chút vấn đề, tuy nhiên, là điều kiện này không làm việc. [Sinh viên] Bạn cần phải lật nó. Đúng, vì vậy điều kiện này sẽ không bao giờ là sự thật ban đầu là cách chúng ta nói chuyện về nó. Chúng tôi muốn làm điều gì đó cho đến khi kết thúc <bắt đầu, nhưng chúng tôi muốn làm một cái gì đó trong khi bắt đầu ≤ cuối. 

Có đảo ngược đó của logic. Tôi tội lỗi làm cho những sai lầm tất cả các thời gian. [Sinh viên] Tại sao nó có được ít hơn hoặc bằng? Bởi vì bạn có nhớ là trường hợp mà chúng tôi đã đến nơi mà chỉ có một phần tử, và chúng tôi đã giảm, và chúng tôi đang tìm kiếm tại chỉ là 15 trong mảng của chúng tôi? Của chúng tôi và bắt đầu và kết thúc của chúng tôi là cùng một nguyên tố. Chúng tôi muốn đảm bảo rằng chúng tôi xử lý trường hợp. Nếu chúng ta làm một thẳng ít hơn, chúng tôi sẽ chỉ có thể để có được một mảng 2-yếu tố. Một khi chúng ta đã xuống đến yếu tố cuối cùng đó, nếu như đó là yếu tố của chúng tôi, chúng tôi sẽ không bao giờ tìm thấy nó. Bây giờ đây, chúng ta có thể làm chính xác như bạn đã nói. Chúng ta có thể bắt đầu nhúng cả các công cụ vào giữa của vòng lặp trong khi của chúng tôi. Chúng tôi có thể tiếng tom trong điểm giữa của chúng tôi. Chúng tôi có thể mất tất cả các nếu báo cáo, kéo họ ra khỏi vòng lặp do-trong khi, tiếng tom chúng vào, làm sạch những thứ lên một chút, và tôi sẽ đi trước và lưu sửa đổi này. Và tại thời điểm này, chúng tôi đang nhận được khá gần. Sam. Tôi nghĩ bạn cũng cần phải có int trung điểm = kích thước 1/2. Đã nhận nó, kích thước 1/2. Có bất cứ điều gì khác chúng ta cần phải thay đổi về dòng đó? Đó là một nắm bắt tốt. 

Kích thước làm gì? Chúng tôi bao giờ thay đổi kích thước? Để giữ dòng như thế này, chúng ta phải thay đổi kích thước. Chúng ta phải thay đổi kích thước mỗi lần chúng tôi đi xung quanh cho vòng lặp. Nhưng hãy nhớ rằng khi chúng tôi đi qua ví dụ của chúng ta chỉ là một chút trước đó, và chúng tôi đã bắt đầu từ 4 và kết thúc tất cả các cách trên 108? Làm thế nào chúng tôi tính toán trung điểm? Chúng ta sử dụng kích thước? Hay chúng ta đang sử dụng bắt đầu và kết thúc thay vì? Đó là sự khác biệt giữa kết thúc và bắt đầu. Chính xác, và làm thế nào chính xác tôi nên viết rằng, Charlotte? Chỉ kết thúc - bắt đầu. Bạn sẽ không cần phải làm gì - 1 bởi vì - 1 đã được bao gồm trong các kết thúc và bắt đầu đã. [Nate] Great, bạn hoàn toàn đúng. Chúng tôi không có làm - 1 - 1 đã được bao gồm và hạch toán vì khi chúng ta khởi tạo biến kết thúc. 

Có bất cứ điều gì khác tôi cần phải làm cú pháp để có dòng này có ý nghĩa? [Sinh viên] Thêm bắt đầu >> Plus. Bắt đầu? [Sinh viên] Khi kết thúc. Bởi vì nó chỉ được tính toán một nửa chiều dài. Bạn cần phải thêm bắt đầu. [Nate] Điều này sẽ tính toán cho chúng ta? Nếu chúng ta nghĩ về kết thúc vào ngày này lặp đi lặp lại đầu tiên của vòng lặp, cuối cùng là có được trong 7 chỉ số vị trí. Bắt đầu là ở vị trí 0. Hãy nhớ rằng, chúng tôi đang tìm kiếm cho một trong hai vị trí 3 hoặc vị trí thứ 4. Nếu chúng ta nhìn vào toán học này, chỉ để làm cho nó một ít hữu hình hơn, đặt một số số ở đây, chúng tôi có 7, 0, vì vậy 7 - 0, và sau đó / 2 là 3 trong phân chia số nguyên, đó là. Sau đó, chúng ta cần phải sau đó thêm lại bắt đầu của chúng tôi? Chúng tôi làm không phải trong trường hợp này. Trên lặp đầu tiên, nó sẽ được sử dụng tốt bởi vì bắt đầu là 0. Nhưng như chúng ta tiến bộ, chúng tôi thực sự tất cả chỉ cần cuối cùng bắt đầu / 2. Có một trick ở đây, và đó là là một ưu tiên. [Sinh viên] Chúng ta có cần dấu ngoặc đơn? [Nate] Chính xác, đó là bởi vì nếu chúng ta không đặt các dấu ngoặc đơn, sau đó dòng này sẽ được giải thích thay vì (kết thúc) - (bắt đầu / 2), mà chúng tôi chắc chắn không muốn. Xem ra cho những quy tắc ưu tiên. [Sinh viên] Tại sao không phải là nó kết thúc + bắt đầu? Tại sao không phải là nó kết thúc + bắt đầu? [Sinh viên] Tại sao nó không đó? Tại sao nó sẽ là +? Tôi nghĩ rằng bạn đã đúng. [Sinh viên] Bởi vì đó là trung bình? [Nate] End + bắt đầu, bạn đã hoàn toàn đúng. Wow, tôi hoàn toàn goofed. Bạn nói đúng. Nếu chúng tôi đã làm trừ, chúng ta sẽ muốn thêm bắt đầu trở lại. Trong trường hợp này, bạn rất đúng rằng chúng ta muốn lấy trung bình của hai, vì vậy chúng tôi muốn thêm chúng, như trái ngược trừ chúng. [Sinh viên] Nó cũng sẽ làm việc nếu bạn đã kết thúc - bắt đầu / 2 + bắt đầu. Nó sẽ nếu chúng tôi làm Tôi tin như vậy. 

Ví dụ, nếu chúng ta đang tìm kiếm bắt đầu, và chúng tôi đã dời qua đây với 15. Bây giờ bắt đầu là ở vị trí 2. Cuối cùng là ở vị trí 7. Nếu chúng tôi loại trừ họ, chúng tôi nhận được 5. Chia cho 2, chúng tôi nhận được 2. Và sau đó chúng tôi thêm 2 trở lại trong, và rằng chúng ta có được vị trí thứ 4, mà là ngay ở đây, mà là trung điểm. [Sinh viên] chúng tôi cần phải chăm sóc ngắt? Trong ý thức những gì chúng ta cần phải chăm sóc của gói? Nếu số tiền hoặc sự khác biệt giữa tùy thuộc vào cách chúng ta làm điều đó không phải là một số chẵn. Sau đó, máy tính bị nhầm lẫn cho dù khi đó là 2,5; để bạn di chuyển sang bên trái hoặc bên phải để xác định là trung điểm? Đã nhận nó. Nó chỉ ra rằng với phân chia số nguyên, chúng ta không bao giờ nhận được những số điểm nổi. Chúng tôi không bao giờ có được các số thập phân. Nó hoàn toàn bị loại bỏ. Nếu bạn có một máy tính phân chia hai biến int, và một là 7, và khác là 2, bạn sẽ không nhận được 3,5 kết quả là. Nó sẽ có được 3. Phần còn lại sẽ được loại bỏ, vì vậy nó có hiệu quả làm tròn- không phải một vòng mà là một tầng, nếu bạn đã quen thuộc với môn toán, nơi bạn hoàn toàn loại bỏ các số thập phân, và do đó bạn đang chủ yếu cắt bỏ nó xuống gần nhất toàn bộ vị trí, số nguyên gần nhất. [Sinh viên] Nhưng sau đó sẽ là vấn đề bởi vì nếu bạn có một mảng của 7 yếu tố sau đó tự động các yếu tố thứ 3 của trung điểm thay vì 4. Làm thế nào để chúng ta đối phó với điều đó? Đó là vấn đề bởi vì nếu chúng ta có một mảng của 7, nó sẽ chọn thứ 3 thay vì 4. Ông có thể giải thích thêm một chút? [Sinh viên] Bởi vì nếu bạn có 7 yếu tố sau đó các yếu tố thứ 4 là trung điểm, phải không? Ghi lời nhận xét của bạn về là số không được lập chỉ mục, mặc dù. [Sinh viên] Yeah, vì vậy ở vị trí 3. Điều đó sẽ là trung điểm. Yeah. Oh, okay. Tôi thấy những gì bạn có ý nghĩa. Đó là loại lạ, như chúng ta đã quen với khái niệm này toàn bộ loại bỏ thập phân. Đó là một điểm tuyệt vời. Hãy hoàn thành điều này. Chúng tôi đã tính toán trung điểm của chúng tôi. 

Chúng tôi đang thử nghiệm để xem nếu kim của chúng tôi là bằng với giá trị trung bình. Chúng tôi đang in mà chúng tôi tìm thấy nó, nhưng thực sự, những gì chúng ta muốn làm gì trong tình huống này? Chúng tôi đã tìm thấy nó, vì vậy chúng tôi muốn cho người gọi biết rằng chúng tôi tìm thấy nó. Chúng tôi đã có một chức năng mà là một chức năng kiểu boolean. Cách chúng ta ra hiệu cho các người gọi của chức năng của chúng tôi rằng chúng tôi sẵn sàng để đi là chúng ta nói, "Này, điều này là đúng sự thật." Làm thế nào chúng tôi sẽ làm điều đó, Kevin? Bạn gật đầu của bạn. >> [Kevin] Thêm return true. [Nate] Chính xác, trở lại đúng sự thật. Bây giờ, nếu nó không bằng nhau, làm thế nào chúng ta sẽ xem xét ở nửa bên trái? Bất cứ ý tưởng? Stella, bất kỳ ý tưởng? Bạn cần phải thiết lập một vị trí mới cho người dùng cuối cùng. Yeah. Vì vậy, chúng ta phải làm vị trí trung điểm cuối cùng. Lớn. Chúng ta cần phải thiết lập một vị trí mới cho cuối cùng nhìn vào nửa bên trái. Đây là những gì chúng tôi nói chuyện về trước khi mà Tôi tiếp tục trở lại với ví dụ này. Tôi đã bắt đầu ở đây, và sau đó tôi có kết thúc tất cả các cách trên đây. 

Một lần nữa, nếu chúng ta đang tìm kiếm cho 15, và trung điểm của chúng tôi là ở tuổi 16, và chúng tôi nhận ra, "Rất tiếc, 16 là lớn. Chúng tôi muốn chuyển sang nửa bên trái. " Chúng tôi sau đó sẽ di chuyển kết thúc với 15, và chúng tôi làm điều đó bằng cách dùng một từ trung điểm và thiết lập như kết thúc mới của chúng tôi. Tương tự như vậy, nếu chúng ta muốn nhìn vào nửa bên phải, làm thế nào chúng tôi sẽ làm điều đó? Bạn có một ý tưởng? [Sinh viên] Bạn chỉ cần đặt bắt đầu trung điểm + 1. [Nate] Great. Và giờ đây, trong trường hợp mà chúng tôi không tìm thấy bất cứ điều gì, mà có được chăm sóc cho chúng ta? Daniel, mà có được đưa về chăm sóc cho chúng ta? [Daniel] số [Nate] Nếu chúng ta làm cho nó thông qua toàn bộ mảng và chúng tôi không tìm thấy bất cứ điều gì, nơi đó sẽ được đưa về chăm sóc, hoặc chúng ta nên chăm sóc nó? Daniel] điều kiện trong khi. [Nate] Yeah, các điều kiện trong khi, chính xác. Nó sẽ chăm sóc đi qua toàn bộ mảng nếu chúng ta không tìm thấy bất cứ điều gì. Trong khi vòng lặp này sẽ kết thúc. Chúng tôi sẽ không bao giờ gặp phải tình trạng này, và chúng tôi có thể trả về false. Chúng tôi cũng có thể để lại điều này nếu ở đây như thế này vì nếu điều này nếu tuyên bố là đúng sự thật, và chức năng của chúng tôi sẽ trở lại, và vì vậy chúng tôi sẽ cơ bản hủy bỏ chức năng này vào thời điểm này khi chúng ta trở lại đúng sự thật. Nhưng điều gì sẽ xảy ra với cấu trúc này ở đây? Điều này sẽ làm việc hoàn toàn, hoặc là có một số lỗ hổng logic trong đó? 

Có một số lỗ hổng logic trong đó, với cách thức mà nó đã được thiết lập. Nó có thể là gì? [Sinh viên] Tại sao bạn cần - và + 1 giây? Điều này tạo mảng của chúng tôi là mới nửa trái và nửa bên phải của chúng tôi. [Sinh viên] Nhưng tại sao bạn không thể làm điều đó mà không có 1 và + 1 giây? [Nate] Chúng ta có thể thiết lập nó bằng trung điểm? Điều gì có thể là vấn đề về điều đó? [Sinh viên] Tôi đoán nó không hiệu quả bởi vì bạn đang kiểm tra một giá trị đã được kiểm tra. [Nate] Chính xác, do đó, Sam là hoàn toàn đúng. Nếu bạn thiết lập cuối cùng và bắt đầu bằng điểm giữa thay vì - 1 + 1 suy, tại một số điểm trong tương lai, chúng tôi sẽ kết thúc kiểm tra trung điểm một lần nữa. [Sinh viên] Tôi bắt đầu các pset, và sau đó tôi đã có một cái gì đó như thế Tôi quên 1 +, và nó đã bị mắc kẹt trong một vòng lặp vô hạn. Đúng, bởi vì tại một số điểm bạn sẽ không bao giờ đi để có được bắt đầu và kết thúc để thực sự chồng chéo lên nhau. Cool. Có một lỗ hổng logic hơn, và đó là điều này chắc chắn sẽ có một khác nếu. Tại sao có thể được? 

Lý do là nếu nó không phải là một khác nếu bạn nhìn thấy nó, Kevin? [Kevin] Yeah, bởi vì bạn đang thay đổi điểm kết thúc. [Nate] Chính xác. Chúng tôi đang thay đổi các thiết bị đầu cuối, và nếu nó được viết như thế này-we'll không gian giữa các nó sẽ kiểm tra trường hợp này. Trường hợp này, nếu nó thành công, sẽ hủy bỏ ra khỏi chức năng. Sau đó, nó sẽ kiểm tra trường hợp này, và nếu điều này thành công, nó sẽ điều chỉnh các thiết bị đầu cuối, và sau đó nó sẽ tiếp tục và kiểm tra trường hợp này. Nhưng vào thời điểm này, chúng tôi không muốn nó tiếp tục kiểm tra. May mắn thay, chúng tôi đã không thiết lập lại điểm giữa ở đây, và chúng tôi biết rằng trường hợp này sẽ không thành công. Nhưng chúng tôi chắc chắn muốn đặt khác nếu có mặc dù điều đó có thể-trong trường hợp này vì chúng tôi không điều chỉnh trung điểm, sẽ tạo sự khác biệt? Không, bởi vì những trường hợp này là tất cả độc quyền. Một lần nữa, tôi xấu. Chúng tôi không, tôi nghĩ rằng, cần điều này nếu người nào khác. Chúng tôi có thể cung cấp cho nó một thử và chạy nó và xem những gì sẽ xảy ra. Xây dựng, một lỗi xảy ra. Đây có thể là bởi vì tôi rời những b và e ở đây. Tôi có thêm lên những ở đầu trang? Nó không giống như nó. Chúng tôi thu nhỏ, xây dựng, có nó đi, vì vậy bây giờ nếu chúng ta tìm kiếm 15, Vâng. Hãy để tôi phóng to. 15, có. Chúng tôi có thể chạy nó một lần nữa. Tải lên mã nguồn, xây dựng, chạy. Chúng tôi có thể tìm kiếm một cái gì đó như 13, và chúng tôi không nhận được bất cứ điều gì in ra, vì vậy nó không tìm thấy điều đó cho chúng ta. Đó là tuyệt vời, bởi vì nó không có trong danh sách của chúng tôi. 

Chúng tôi hiện đang hết thời gian. Đó là sẽ có thể là trong tuần này. Cảm ơn bạn đã tham gia, và nhìn thấy bạn sau này. 

[CS50.TV]