Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thỏa mãn điều kiện gì?

Câu hỏi: Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thỏa mãn điều kiện gì? Nếu không thỏa mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?

Lời giải:

- Quan sát Hình 15.1

- Thuật toán tìm kiếm tuần tự: tìm kiếm lần lượt từ đầu danh sách cho đến khi tìm được

- Thuật toán tìm kiếm nhị phân: so sánh giá trị ở giữa danh sách đã được sắp xếp với giá trị cần tìm.

Trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần phải được sắp xếp theo quy tắc (theo bảng chữ cái, số thứ tự tăng dần hoặc giảm dần). 

Nếu không thỏa mãn điều kiện đó, thuật toán tìm kiếm nhị phân không thực hiện được.

* Ý tưởng và cơ sở lý thuyết định lý chính của tìm kiếm nhị phân 

Ý tưởng của thuật toán tìm kiếm nhị phân

Chú ý: Trong bài viết tôi giả sử mảng đang sắp xếp tăng dần. Với trường hợp mảng sắp xếp giảm dần, bạn đọc sau khi hiểu thuật toán sẽ có thể tự làm.

Do tính chất mảng đã sắp xếp, công việc tìm kiếm phần tử x có thể triển khai như sau:

Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:

Nếu phần tử arr[mid] = x. Kết luận và thoát chương trình.

Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].

Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].

Cơ sở lý thuyết: Định lý chính của tìm kiếm nhị phân

Khi gặp một bài toán mà ta đoán được có thể dùng tìm kiếm nhị phân để giải, thì ta phải chứng minh tính đúng đắn suy luận của chúng ta. Do đó, xây dựng một cơ sở lý thuyết vững chắc là vô cùng cần thiết. Sau đây là bài toán có thể áp dụng tìm kiếm nhị phân, song song đó là ví dụ thực tế với bài toán mở đầu.

Cho không gian tìm kiếm SS bao gồm các ứng cử viên cho kết quả của bài toán. Ta định nghĩa môt hàm kiểm tra P:S→true,falseP:S→true,false là hàm nhận một ứng cử viên x∈Sx∈S và trả về giá trị true/falsetrue/false cho biết xx có hợp lệ hay không (tùy vào bài toán mà định nghĩa hợp lệ sẽ khác nhau). Hiểu đơn giản, hàm PP là hàm "kiểm tra" một tính chất nào đó, xem một ứng cử viên cho kết quả của bài toán có thỏa tính chất đó không.