Algorithms: searching · Thuật toán: tìm kiếm
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
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.
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
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))
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
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.
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
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))
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
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.
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
Trong伪代码 của 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)
}
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
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ự.
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
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 · Tìm kiếm trong danh sách
Binary search needs a sorted list but is far faster than linear. · Tìm kiếm nhị phân cần một danh sách đã sắp xếp nhưng nhanh hơn nhiều so với tìm kiếm tuyến tính.
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one. · Viết linear_search(lst, target). Trả về chỉ mục của target trong lst, hoặc trả về -1 nếu nó không có ở đó. Kiểm tra từng mục một.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
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. · Viết binary_search(sorted_lst, target) cho một danh sách sắp xếp từ nhỏ đến lớn. Trả về chỉ mục của target, hoặc trả về -1. Xem xét phần tử ở giữa và cắt đôi phạm vi tìm kiếm mỗi lần.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1. · Viết contains(lst, target) trả về True nếu target có trong lst, ngược lại trả về False. Bạn có thể tái sử dụng tìm kiếm tuyến tính và so sánh kết quả với -1.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.