1.1. Bài toán tìm kiếm trên thực tế
- Bài toán 1: Miền dữ liệu là tất cả ảnh trên mạng Internet, kết quả là các ảnh hoa hồng.
- Bài toán 2: Miền dữ liệu là các tệp văn bản trên đĩa cứng, kết quả là tệp bai-hoc-1.docx.
- Bài toán 3: Miền dữ liệu là danh sách học sinh và điểm thi, kết quả là danh sách 5 bạn có điểm trung bình cao nhất.
1.2. Tìm kiếm tuần tự
- Cách An lật thẻ từ đầu đến cuối là tìm kiếm tuần tự trong dãy đối tượng.
- Thuật toán tìm kiếm tuần tự : Cho dãy số A[0], A[1],..., A[n-1] và giá trị K, cần tìm chỉ số i mà A[i] = K, trả về -1 nếu không tìm thấy.
- Thuật toán tìm kiếm tuần tự có thể viết như sau:
1.3. Tìm kiếm nhị phân
a. Phân tích bài toán
- Tìm kiếm nhị phân: tìm kiếm với dãy số đã được sắp xếp.
- Duyệt phần tử bất kì, xác định phần tử cần tìm ở bên trái hay bên phải.
- Quyết định tìm tiếp theo hướng nào mà không cần duyệt tất cả các phần tử của dãy số.
b. Thuật toán tìm kiếm trên thực tế
- Thuật toán tìm kiếm nhị phân thu hẹp phạm vi tìm kiếm liên tục.
- Nếu giá trị của phần tử ở giữa bằng K thì thông báo tìm thấy.
- Nếu K nhỏ hơn giá trị ở giữa, thu hẹp phạm vi tìm kiếm nửa đầu dãy tăng A (ngược lại thì phạm vi tìm kiếm nửa sau).
- Thiết lập left, right là chỉ số phần tử đầu và cuối của dãy cần tìm. Cần tìm K trong A[left..right].
- So sánh K với phần tử giữa dãy A[mid], có 3 trường hợp có thể xảy ra:
+ Nếu K = A[mid] thì trả về chỉ số mid và kết thúc.
+ Nếu K < A[mid] thì phần tử cần tìm ở dãy con bên trái của A[mid], cập nhật right = mid - 1, giữ nguyên left.
+ Nếu K > A[mid] thì phần tử cần tìm ở dãy con bên phải của A[mid], cập nhật left = mid + 1, giữ nguyên right.
- Lặp lại cho đến khi tìm thấy hoặc phạm vi tìm kiếm bằng rỗng (right < left).
c. Minh họa các bước của thuật toán tìm kiếm nhị phân
- Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì số phần tử cần duyệt giảm một nửa sau mỗi vòng lặp.
- Với cùng dãy số A và giá trị tìm kiếm K, thuật toán tìm kiếm tuần tự cần 6 bước, nhưng thuật toán tìm kiếm nhị phân chỉ cần 2 bước.
- Thuật toán tìm kiếm nhị phân trên dãy số đã sắp xếp tăng dần, hàm BinarySearch(A,K) trả lại chỉ số i nếu tìm thấy A[i] = K và -1 nếu không tìm thấy K trong dãy A.
