Bài tập Tìm kiếm nhị phân có đáp án

Em đồng ý với ý kiến của bạn Thanh An.

Vì khi ta chia đôi để tìm một số trong dãy thì ta có thể tìm được kết quả nhanh hơn.

Ta sẽ sắp xếp dãy theo thứ tự không giảm, sau đó chia đôi để tìm kiếm. Nên sẽ không tìm quá ba lần lật thẻ.

Tìm kiếm x = 60.

Bước 1. Ta sắp xếp dãy theo thứ tự không giảm.

Bước 2. Ta chia đôi dãy số để tìm x trong dãy. Ta sẽ chia ngay vị trí a$_{6}$ (a$_{6}$=52) vì x > a$_{6}$. Phạm vi tìm kiếm tiếp theo là từ a$_{7}$ đến a$_{8}$.

Bước 3. Khi đó phạm vi tìm kiếm chỉ có a$_{7}$ đến a$_{8}$ và ta thấy không có số nào bằng x. Kết thúc thuật toán không tìm thấy kết quả x.

Cách tra cứu, tìm giải nghĩa từ điển:

Danh sách các giá trị dữ liệu không được sắp xếp và có thể được thay đổi bằng cách sử dụng các phương thức tích hợp sẵn. Từ điển được sử dụng để tạo ra một bản đồ cho các khóa (keys) độc nhất tới giá trị (values). Từ điển sẽ sắp xếp một tập các đối tượng (khóa) đến một tập các đối tượng là giá trị, do đó người sử dụng có thể tạo ra một danh sách các đối tượng không theo thứ tự. Các từ điển được tạo ra có thể biến đổi được, có nghĩa là chúng có thể được thay đổi tùy theo mục đích của người dùng.

Ta gọi cách tìm kiếm đó là thuật toán nhị phân.

Bước 1. Sắp xếp dãy theo thứ tự không giảm.

Bước 2. Ta chia đôi dãy số để tìm x trong dãy.

Bước 3. Lấy phần tử đứng giữa dãy để so sánh với x.

Nếu phần tử đó chính là x thì kết luận đã tìm thấy x và kết thúc thuật toán.

Ngược lại, ta có thể xác định được x chắc chắn không có trong nửa đầu hay nửa sau của dãy. Từ đó ta xác định được phạm vi tìm kiếm và thực hiện tìm kiếm trong phạm vi nữa dãy còn lại, sẽ được lặp lại theo cách như thế cho đến khi tìm được kết quả.