Algorithms: searching
Những gì chúng ta sẽ làm
- Một thuật toán là danh sách các bước rõ ràng giúp giải quyết một vấn đề.
- Một công việc rất phổ biến là tìm kiếm: tìm xem một giá trị nằm ở đâu trong danh sách.
- Chúng ta sẽ học hai thuật toán: tìm kiếm tuyến tính và tìm kiếm nhị phân.
Tìm kiếm tuyến tính
- Kiểm tra từng mục một cách tuần tự, từ đầu đến cuối.
- Nếu bạn tìm thấy giá trị đó, hãy trả về chỉ số (vị trí) của nó.
- Nếu bạn đi hết mà không bao giờ tìm thấy, hãy trả về
-1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
Tại sao danh sách đã sắp xếp lại hữu ích
- Tìm kiếm tuyến tính hoạt động trên bất kỳ danh sách nào, kể cả những danh lộn xộn.
- Nhưng nếu danh sách được sắp xếp (từ nhỏ đến lớn), chúng ta có thể nhanh hơn nhiều.
- Tìm kiếm nhị phân tận dụng thứ tự sắp xếp để bỏ qua nửa danh sách mỗi lần.
Tìm kiếm nhị phân
- Hãy nhìn vào mục ở giữa.
- Nếu đó chính là mục đích, bạn đã hoàn thành.
- Nếu mục đích nhỏ hơn, hãy tìm ở nửa trái; nếu lớn hơn, tìm ở nửa phải. Lặp lại.
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
Kết hợp các ý tưởng
- Việc tìm kiếm kết hợp ba khối xây dựng cơ bản mà bạn đã biết.
- Sắp xếp trình tự: làm theo thứ tự các bước. Lựa chọn:
if/elif/else. - Lặp: một vòng lặp (
forhoặcwhile) lặp lại việc kiểm tra.
Trong pseudocode AP CSP
- Đề thi thường viết một vòng lặp và điều kiện kiểm tra như thế này.
FOR EACHtruy cập từng mục;IFthực hiện lựa chọn;REPEAT UNTILlặp cho đến khi một điều kiện đúng.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Lỗi thường gặp
- Tìm kiếm nhị phân yêu cầu một danh sách đã sắp xếp.
- Tìm kiếm tuyến tính kiểm tra từng mục theo thứ tự.
Bây giờ bạn thử
- Mỗi nhiệm vụ đều cung cấp tên thủ tục và yêu cầu trả về.
- Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Searching a list
Binary search needs a sorted list but is far faster than linear.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Write contains(lst, target) that returns True nếu target is in lst, else False. You may reuse linear search and compare the result to -1.
Nhấn Chạy để xem kết quả ở đây.