• B1: Nhập x
• B2: x > 30 ?
• B3: In “x > 30”
• B4: In “x ≤ 30”

Bài giải

Dãy số đã cho là:

a1 = 5
a2 = 16
a3 = 20
a4 = 25
a5 = 30
a6 = 35

Cần dùng thuật toán tìm kiếm nhị phân để tìm x = 80.

Vì dãy đã được sắp xếp tăng dần nên ta có thể dùng tìm kiếm nhị phân.

Các bước thực hiện:

Bước 1:

Trái = 1, Phải = 6

Giữa = (1 + 6) : 2 = 3

Ta có:

a3 = 20

So sánh:

20 < 80

Vì a3 < x nên ta tìm tiếp ở nửa bên phải.

Cập nhật:

Trái = 4, Phải = 6

Bước 2:

Giữa = (4 + 6) : 2 = 5

Ta có:

a5 = 30

So sánh:

30 < 80

Vì a5 < x nên ta tiếp tục tìm ở nửa bên phải.

Cập nhật:

Trái = 6, Phải = 6

Bước 3:

Giữa = (6 + 6) : 2 = 6

Ta có:

a6 = 35

So sánh:

35 < 80

Vì a6 < x nên tiếp tục tìm bên phải.

Cập nhật:

Trái = 7, Phải = 6

Bước 4:

Vì Trái > Phải nên thuật toán dừng lại.

Kết luận:

Không tìm thấy x = 80 trong dãy số đã cho.

Mô tả thuật toán tìm kiếm nhị phân bằng lời:

Bắt đầu

Nhập dãy số đã sắp xếp tăng dần và giá trị cần tìm x.

Gán Trái = 1, Phải = n.

Nếu Trái lớn hơn Phải thì kết luận không tìm thấy x.

Ngược lại, tính Giữa = (Trái + Phải) : 2.

Nếu aGiữa = x thì kết luận tìm thấy x tại vị trí Giữa.

Nếu aGiữa < x thì tìm tiếp ở nửa bên phải, gán Trái = Giữa + 1.

Nếu aGiữa > x thì tìm tiếp ở nửa bên trái, gán Phải = Giữa - 1.

Lặp lại cho đến khi tìm thấy x hoặc Trái > Phải.

Kết thúc.