Tư tưởng thuật toán tìm kiếm nhị phân là gì

Question

Tài khoản ẩn danh · Accepted Answer

{"userId": 5410137, "userName": "Trung Tien "}
chúc bạn học giỏi chăm!!!!
Tư tưởng của thuật toán tìm kiếm nhị phân là chia đôi dãy đã sắp xếp để tìm kiếm giá trị cần tìm. Ở mỗi bước, so sánh giá trị giữa với giá trị cần tìm. Nếu bằng, trả về vị trí; nếu nhỏ hơn, tìm ở nửa phải; nếu lớn hơn, tìm ở nửa trái. Quá trình lặp lại cho đến khi tìm thấy hoặc không còn phần tử. Thuật toán này có độ phức tạp O(log n).

Timi · Answer

Tư tưởng thuật toán tìm kiếm nhị phân là dựa trên nguyên tắc "chia để trị" (divide and conquer). Cụ thể, thuật toán này áp dụng cho mảng đã được sắp xếp và hoạt động như sau:

1. Xác định phần tử ở giữa mảng (phần tử trung vị).
2. So sánh phần tử cần tìm với phần tử trung vị:
   - Nếu bằng, trả về vị trí phần tử.
   - Nếu nhỏ hơn, tiếp tục tìm kiếm trong nửa bên trái của mảng.
   - Nếu lớn hơn, tiếp tục tìm kiếm trong nửa bên phải của mảng.
3. Lặp lại quá trình trên với nửa mảng được chọn cho đến khi tìm thấy phần tử hoặc không còn phần tử nào để tìm.

Như vậy, thuật toán tìm kiếm nhị phân liên tục chia nhỏ phạm vi tìm kiếm xuống một nửa, giúp giảm đáng kể số lần so sánh so với tìm kiếm tuần tự, từ đó tăng hiệu quả tìm kiếm.