[MUSIC CHƠI] 

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 loại 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 được thực hiện như một tìm kiếm tuyến tính, nhưng bạn có thể làm nhiều tốt hơn. 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 ví dụ này, số nguyên ba. 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 danh bạ vào giữa trang trong tuần không. 

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, kể từ khi ba, 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 đang phải 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ả như thế nào? Tốt 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ố để nhìn vào, chúng ta giữa của danh sách, và so sánh với 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 return false vì kim chắc chắn không phải là trong đống cỏ khô. 

Bây giờ là một điều thú giả này trong tìm kiếm nhị phân là nó có thể được giải thích hoặc như một 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 Tất nhiên, nhưng tôi biết rằng nó là một lựa chọn nếu bạn muốn thử. 

Bây giờ chúng ta hãy nhìn vào loại. Loại có một mảng và các số nguyên n, mà là kích thước của mảng. Hiện nay có nhiều loại khác nhau của các loại, và bạn có thể xem xét một số quần short cho trình diễn và giải thích. Kiểu trả về cho chúng tôi chức năng sắp xếp có hiệu lực. Vì vậy, đó có nghĩa là chúng tôi sẽ không trở về mảng bất kỳ từ loại. Chúng tôi đang thực sự sẽ thay đổi rất mảng đã được thông qua vào chúng tôi. 

Và đó là có thể bởi vì mảng là thông qua tham khảo trong C. Bây giờ chúng ta sẽ xem thêm về điều này sau, nhưng sự khác nhau giữa đi qua trong một cái gì đó giống như một số nguyên và đi qua trong một mảng, là khi bạn vượt qua trong một số nguyên, C là chỉ cần đi để tạo một bản sao của số nguyên đó và vượt qua nó để chức năng. Biến ban đầu sẽ không thay đổi một khi chức năng được hoàn tất. Với một mảng, mặt khác, nó sẽ không làm cho một bản sao, và bạn sẽ thực sự được chỉnh sửa rất mảng chính nó. 

Vì vậy, một loại loại là các loại lựa chọn. Việc lựa chọn loại hoạt động bằng cách bắt đầu từ đầu, và sau đó bạn lặp hơn và tìm thấy những yếu tố nhỏ nhất. Và sau đó bạn thay đổi đó nhỏ nhất phần tử với các đầu tiên. Và sau đó bạn di chuyển đến phần tử thứ hai , Tìm nhỏ nhất tiếp theo yếu tố, và sau đó trao đổi rằng với sự Yếu tố thứ hai trong mảng bởi vì phần tử đầu tiên đã được sắp xếp. Và như vậy thì bạn tiếp tục cho mỗi yếu tố trong việc xác định nhỏ nhất giá trị và trao đổi nó ra. 

Đối với tôi bằng 0, yếu tố đầu tiên n trừ đi 1, bạn sẽ so sánh mỗi giá trị tiếp theo sau đó và tìm thấy chỉ số của các giá trị tối thiểu. Một khi bạn tìm thấy chỉ số giá trị tối thiểu, bạn có thể trao đổi có giá trị của mảng tối thiểu và mảng I. 

Một loại loại mà bạn có thể thực hiện là bong bóng sắp xếp. Vì vậy, lặp đi lặp lại bong bóng sắp xếp trên danh sách so sánh các yếu tố lân cận và trao đổi các yếu tố là theo thứ tự sai. Và theo cách này, yếu tố lớn nhất sẽ bong bóng để kết thúc. Và danh sách được sắp xếp một lần nữa yếu tố đã được đổi chỗ. 

Vì vậy, đó là hai ví dụ về các loại các thuật toán mà bạn có thể thực hiện cho chương trình tìm. Một khi bạn hoàn thành sắp xếp, và bạn đã thực hiện tìm kiếm, bạn đã hoàn tất. Tên tôi là Zamyla, và đây là CS50. 

[MUSIC CHƠI]