Tip:
Highlight text to annotate it
X
>> [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à *** bóng sắp xếp.
Vì vậy, lặp đi lặp lại *** 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ẽ *** 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]