Searching · Tìm kiếm
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
English
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
Tiếng Việt
Tìm kiếm trong danh sách
- Tìm kiếm có nghĩa là xác định xem một giá trị có tồn tại trong danh sách hay không, và nằm ở đâu.
- Câu trả lời thông thường là chỉ mục của giá trị đó, hoặc
-1nếu nó không có mặt. - Hai phương pháp cổ điển là tìm kiếm tuyến tính và tìm kiếm nhị phân.
English
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
Tiếng Việt
Tìm kiếm tuyến tính
- Kiểm tra từng phần tử một theo thứ tự, bắt đầu từ đầu.
- Dừng lại ngay khi tìm thấy một giá trị khớp.
- Nó hoạt động trên bất kỳ danh sách nào, đã sắp xếp hay chưa.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
English
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
Tiếng Việt
Tìm kiếm nhị phân
- Tìm kiếm nhị phân yêu cầu một danh sách đã sắp xếp.
- Xem xét phần tử giữa. Nếu nó là mục tiêu, dừng lại.
- Nếu mục tiêu nhỏ hơn, tìm kiếm nửa bên trái; nếu lớn hơn, tìm kiếm nửa bên phải.
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
English
Compare them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
Tiếng Việt
So sánh chúng
- Tìm kiếm tuyến tính có thể kiểm tra tất cả các phần tử — chậm đối với danh sách dài.
- Tìm kiếm nhị phân loại bỏ một nửa danh sách mỗi bước, nên nó nhanh hơn nhiều.
- Nhưng tìm kiếm nhị phân chỉ hoạt động nếu dữ liệu đã được sắp xếp sẵn.
English
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
Tiếng Việt
Trong pseudocode Cambridge
- Lưu ý
DIVlà phép chia số nguyên (Python sử dụng//).
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
English
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
Tiếng Việt
Lỗi thường gặp
- Tìm kiếm nhị phân cần một danh sách đã sắp xếp; nó thu hẹp phạm vi đi một nửa mỗi bước.
- Tìm kiếm tuyến tính hoạt động trên bất kỳ danh sách nào nhưng chậm hơn.
English
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
Tiếng Việt
Bây giờ bạn thử
- Trả về chỉ mục của giá trị, hoặc
-1khi không tìm thấy. - Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Explore · Khám phá
Linear vs binary search · Tìm kiếm tuyến tính so với tìm kiếm nhị phân
Binary search halves the list each step — far fewer comparisons. · Tìm kiếm nhị phân chia đôi danh sách mỗi bước — ít phép so sánh hơn nhiều.
Write linear_search(items, target) that returns the index of target in items, or -1 if it is not there. Check the items one by one. · Viết linear_search(items, target) trả về chỉ số của target trong items, hoặc -1 nếu không tìm thấy. Kiểm tra từng phần tử một.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step. · Viết binary_search(items, target) cho danh sách đã sắp xếp. Trả về chỉ số của target, hoặc -1 nếu thiếu. Chia đôi phạm vi mỗi bước.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write first_negative(items) that scans the list and returns the index of the first number less than 0, or -1 if there are none. · Viết first_negative(items) quét danh sách và trả về chỉ số của số đầu tiên nhỏ hơn 0, hoặc -1 nếu không có.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.