em hãy viết các bước lặp thực hiện thuật toán tìm kiếm nhị phân để tìm tên bạn "Trang" trong danh sách như hình sau
Quảng cáo
2 câu trả lời 275
Để tìm kiếm tên "Trang" trong danh sách bằng thuật toán tìm kiếm nhị phân, chúng ta cần thực hiện các bước sau:
1. **Sắp xếp danh sách theo thứ tự tăng dần**: Đảm bảo rằng danh sách đã được sắp xếp theo thứ tự tăng dần. Nếu danh sách chưa được sắp xếp, ta cần sắp xếp lại trước khi bắt đầu tìm kiếm.
2. **Đặt hai con trỏ, left và right**:
- left: Trỏ đến phần tử đầu tiên của danh sách.
- right: Trỏ đến phần tử cuối cùng của danh sách.
3. **Lặp cho đến khi left <= right**:
- Tính toán chỉ số trung tâm mid = (left + right) / 2.
- So sánh tên tại chỉ số mid với tên cần tìm kiếm "Trang":
- Nếu tên tại mid là "Trang", trả về mid (tìm thấy).
- Nếu tên tại mid < "Trang", left = mid + 1 (chuyển sang phần bên phải của mảng).
- Nếu tên tại mid > "Trang", right = mid - 1 (chuyển sang phần bên trái của mảng).
4. **Trả về -1 nếu không tìm thấy tên "Trang" trong danh sách**.
Dưới đây là mã Python minh họa cho thuật toán tìm kiếm nhị phân:
`python
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Danh sách đã được sắp xếp
names = ["Anh", "Bình", "Hải", "Lan", "Mai", "Trang", "Vân", "Xuân"]
target_name = "Trang"
result = binary_search(names, target_name)
if result != -1:
print(f"Found {target_name} at index {result}.")
else:
print(f"{target_name} not found in the list.")
`
Khi chạy mã này, nếu tên "Trang" được tìm thấy trong danh sách, chương trình sẽ in ra "Found Trang at index X", nếu không sẽ in ra "Trang not found in the list."
Quảng cáo