[Powered by Google Translate] [Tìm kiếm tuyến tính]
[Patrick Schmid, Đại học Harvard]
[This Is CS50.] [CS50.TV]
Tìm kiếm là một cái gì đó mà bạn có thể làm nhiều hơn bạn nghĩ.
Rõ ràng, mỗi khi bạn mở một trình duyệt web
và tìm kiếm cho một trang web
hoặc tìm kiếm cho bạn bè của bạn trên trang web yêu thích mạng xã hội của bạn -
bạn đang tìm kiếm.
Nhưng đó chỉ là một phần nhỏ trong việc tìm kiếm mà bạn làm trên một cơ sở hàng ngày.
Khi bạn muốn tìm là một trong những chiếc áo xanh trong tủ quần áo,
hoặc áo màu đỏ hoàn hảo cho dịp này,
bạn đang tìm kiếm.
Khi bạn đi đến một cửa hàng mà bạn chưa bao giờ đến trước khi,
và bạn đang tìm kiếm bông cải xanh trong lối đi sản phẩm
bạn đang tìm kiếm.
Những gì bạn có thể đã bắt đầu để ý
là tùy thuộc vào những gì bạn đang tìm kiếm
hoặc các mục được tổ chức như thế nào khi bạn đang tìm kiếm chúng
nó có một hiệu lực về việc làm thế nào bạn tìm kiếm.
Ví dụ, nếu áo sơ mi của bạn được treo trong tủ quần áo,
bạn có thể có lẽ chỉ cần chọn nó ra mà không có nhiều tìm kiếm.
Nếu bạn đang giả định bạn phải đi bộ xuống các lối đi
để có được bông cải xanh, bạn có thể phải xem xét tất cả các loại rau khác
trước khi bạn thấy rằng bông cải xanh.
Tìm kiếm tuyến tính là một ví dụ về một trong những phương pháp như vậy - hoặc thuật toán tìm kiếm.
Như tên của nó,
phương pháp này tìm kiếm cho một mục trong một thời trang tuyến tính, một sau khi khác.
Vì vậy, khi bạn đang tìm kiếm các kết quả từ công cụ tìm kiếm ưa thích của bạn
và bạn đọc danh sách kết quả,
bạn đang sử dụng tìm kiếm tuyến tính.
Okay. Hãy xem một ví dụ.
Nói rằng chúng tôi có một danh sách các số 2, 4, 0, 5, 3, 7, 8, và 1 -
và chúng tôi đang tìm kiếm số 0.
Rõ ràng, bạn chỉ có thể thấy rằng 0 là ở vị trí thứ ba.
Tuy nhiên, một chương trình máy tính mà không phải là may mắn.
Nó chỉ có thể "nhìn thấy" số một tại một thời điểm.
Vì vậy, bắt đầu từ đầu danh sách,
nó chỉ "nhìn thấy" 2.
Chương trình sau đó kiểm tra là 2 bằng 0?
Rõ ràng là không. Vì vậy, nó đi đến số tiếp theo, 4.
4 0 bằng nhau không? Nope.
Tiếp theo, 0. Ah! Zero là bằng 0.
Hiện chúng tôi có nó! Đó là ở vị trí thứ ba.
Okay. Hãy nhìn vào một số giả.
Nó chỉ là một vài dòng dài, nhưng chúng ta hãy nhìn vào nó một dòng tại một thời điểm.
Trước tiên, hãy xác định các chức năng - và chúng tôi sẽ gọi nó là tuyến tính tìm kiếm -
và phải mất hai đối số - chìa khóa và mảng.
Điều quan trọng là giá trị mà chúng ta đang tìm kiếm,
do đó, trong ví dụ trước, đó là số không.
Một mảng là một danh sách các số
có tất cả các giá trị mà chúng ta sẽ tìm kiếm.
Vì vậy, những gì chúng tôi muốn làm là chúng tôi muốn xem xét -
từ tất cả các vị trí, do đó, bắt đầu từ khi bắt đầu của mảng
đến tận phút cuối cùng của mảng nên chiều dài của mảng -
nhìn vào tất cả các vị trí duy nhất và kiểm tra mỗi một.
Vì vậy, đó là những gì mà "cho" vòng lặp được thực hiện.
Và ở từng vị trí, chúng ta sẽ nói
"Đó là giá trị tại vị trí đó hiện tại bằng phím mà chúng ta đang tìm kiếm?"
Vì vậy, trong ví dụ trước một lần nữa, quan trọng là 0 -
vì vậy chúng tôi đang nói đến "mảng tại vị trí tương đương về không?"
Nếu có, chúng ta sẽ quay trở lại 'i' bởi vì đó là vị trí hiện tại chúng ta đang ở.
Vì vậy, trong ví dụ trước,
đó là vị trí thứ ba.
Nếu chúng ta đã trải qua toàn bộ mảng
và chúng tôi đã không tìm thấy bất cứ điều gì -
vì vậy hãy nói rằng chúng tôi đang tìm kiếm con số 500
rõ ràng là không phải trong ví dụ đó
chúng tôi phải trả lại một cái gì đó,
và chúng ta sẽ trở về -1.
Và chúng tôi chỉ trả lại -1 bởi vì đó là một vị trí
không tồn tại trong mảng.
Và như vậy có nghĩa là khi bạn nhận được nó trở lại từ một hàm
"Hmm, okay. Tôi đoán tôi đã không tìm thấy bất cứ điều gì.
Vì vậy, mà 500 không bao giờ ở đó. "
Những điều tốt đẹp về tìm kiếm tuyến tính là
nó sẽ làm việc trên bất kỳ danh sách các mục,
bất kể các mục được sắp xếp như thế nào.
Nó không quan trọng nơi bông cải xanh là trong lối đi sản phẩm.
Như khi bạn đi bộ xuống các lối đi từ đầu đến cuối,
bạn đang bị ràng buộc để tìm thấy nó,
giả sử các cửa hàng đã không chạy ra khỏi bông cải xanh, tất nhiên.
Tuy nhiên, sức mạnh lớn nhất cũng là điểm yếu lớn nhất của nó.
Giả sử bạn có một danh sách 200 số
đều được sắp xếp từ 1 đến 200.
Nếu bạn đang tìm kiếm cho số 198,
bạn phải tìm kiếm gần như toàn bộ danh sách các con số
trước khi bạn tìm thấy một trong những bạn đang tìm kiếm.
Có phải là một cách tốt hơn!
Hãy yên tâm là có.
Nhưng, đó là một chủ đề cho video khác.
Ngoài ra, không băn khoăn!
Chỉ vì tìm kiếm tuyến tính không phải là giải pháp tốt nhất trong mọi tình huống,
nó không có nghĩa rằng nó không có ích.
Nếu không, làm thế nào bạn sẽ tìm thấy rằng bông cải xanh trong lối đi sản phẩm?
Tên tôi là Patrick Schmid, và đây là CS50.
[CS50.TV]