Tìm kiếm
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.
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)
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)
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.
Trong pseudocode Cambridge
- Lưu ý
DIVlà phép chia số nguyên (Python sử dụng//). - Mảng Cambridge thường chạy từ 1 đến
n, số lượng mục.LENGTH()dùng cho chuỗi, nên vòng lặp sử dụngn.
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
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.
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.
Tìm kiếm tuyến tính so với tìm kiếm nhị phân
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.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
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
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.
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
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ó.
Nhấn Chạy để xem kết quả ở đây.