– 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.

 

– 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:

 

– 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ố.

 

– 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).

 

– 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.