ZAMYLA CHAN: Điều đầu tiên bạn có thể thông báo về tìm là chúng ta đã có mã viết cho chúng ta. Này được gọi là đang phân phối. Vì vậy, chúng tôi không chỉ viết riêng của chúng tôi mã từ đầu nữa. Thay vào đó, chúng ta điền vào các khoảng trống ở một số mã đã có từ trước. 

Chương trình sẽ nhắc cho find.c số để điền vào các đống cỏ khô, tìm kiếm các đống cỏ khô cho một người dùng gửi kim, và nó thực hiện điều này bằng cách gọi loại và tìm kiếm, chức năng xác định trong helpers.c. Vì vậy, find.c được viết rồi. Công việc của bạn là viết những người giúp đỡ. 

Vì vậy, những gì chúng ta làm gì? Chúng tôi đang thực hiện hai chức năng. Tìm kiếm, trả về đúng nếu một giá trị được tìm thấy trong đống cỏ khô, trở về sai nếu giá trị là không trong đống cỏ khô. Và sau đó chúng tôi cũng đang thực hiện sắp xếp, mà sắp xếp các mảng được gọi là giá trị. Vì vậy, hãy giải quyết tìm kiếm. 

Tìm kiếm hiện đang thực hiện như một tìm kiếm tuyến tính. Nhưng bạn có thể làm tốt hơn nhiều hơn thế. Tìm kiếm tuyến tính được thực hiện trong O n thời gian, mà là khá chậm, mặc dù nó có thể tìm kiếm bất kỳ danh sách cho nó. Công việc của bạn là để thực hiện tìm kiếm nhị phân, đã chạy thời gian O của log n. Đó là khá nhanh. 

Nhưng có một quy định. Tìm kiếm nhị phân chỉ có thể tìm kiếm thông qua danh sách được sắp xếp trước. Tại sao vậy? Vâng, chúng ta hãy xem một ví dụ. Đưa ra một mảng các giá trị, các đống cỏ khô, chúng ta sẽ được tìm kiếm cho một cây kim, và trong này Ví dụ, số nguyên 3. 

Cách mà tìm kiếm nhị phân hoạt động là chúng ta so sánh giá trị giữa các mảng kim, nhiều như thế nào chúng tôi đã mở một cuốn sách điện thoại vào giữa trang trong Tuần 0. Vì vậy, sau khi so sánh giá trị giữa để kim, bạn có thể loại bỏ một trong hai trái hoặc nửa bên phải của mảng bằng cách thắt chặt giới hạn của bạn. Trong trường hợp này, vì 3, kim của chúng tôi, là ít hơn 10, giá trị giữa, đúng ràng buộc có thể giảm. 

Nhưng cố gắng làm cho giới hạn của bạn như chặt chẽ nhất có thể. Nếu giá trị trung không phải là kim, sau đó bạn biết rằng bạn không cần phải bao gồm nó trong tìm kiếm của bạn. Vì vậy, bên phải của bạn bị ràng buộc có thể thắt chặt giới hạn tìm kiếm nhiều hơn một chút xíu, vv và vv, cho đến khi bạn tìm thấy kim của bạn. 

Vì vậy, những gì hiện các giả đang như thế nào? Vâng, trong khi chúng tôi vẫn đang tìm kiếm thông qua danh sách và vẫn còn có các yếu tố để xem xét trong, chúng ta giữa danh sách và so sánh giá trị trung bình đến kim của chúng tôi. Nếu chúng bằng nhau, thì có nghĩa là chúng tôi đã tìm thấy kim, và chúng ta có thể return true. 

Nếu không, nếu kim nhỏ hơn giá trị trung bình, sau đó có nghĩa là chúng tôi có thể loại bỏ nửa bên phải và chỉ tìm kiếm bên trái của mảng. Nếu không, chúng tôi sẽ tìm kiếm phía bên phải của mảng. Và cuối cùng, nếu bạn không có bất kỳ nhiều yếu tố còn lại để tìm kiếm nhưng bạn đã không tìm thấy kim của bạn chưa, sau đó bạn trở lại sai. Vì kim chắc chắn không có trong đống cỏ khô. 

Bây giờ, có một điều gọn về giả này mã trong tìm kiếm nhị phân là nó có thể được hiểu là một hoặc lặp đi lặp lại hoặc thực hiện đệ quy. Vì vậy, nó sẽ là đệ quy nếu bạn gọi chức năng tìm kiếm trong tìm kiếm hoạt động ở hai nửa của mảng. Chúng tôi sẽ giới thiệu đệ quy một chút sau này trong khóa học. Nhưng tôi biết rằng nó là một lựa chọn nếu bạn muốn thử.