Bài toán tìm vùng chỉ số của dãy đã sắp xếp

Với giải Vận dụng 2 trang 36 Chuyên đề Tin học 11 Kết nối tri thức chi tiết trong Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

Bài toán tìm vùng chỉ số của dãy đã sắp xếp

Vận dụng 2 trang 36 Chuyên đề Tin học 11: Bài toán tìm vùng chỉ số của dãy đã sắp xếp

Thiết lập thuật toán chia để trị để giải bài toán sau: Cho trước dãy A gồm n phần tử đã được sắp xếp theo thứ tự tăng dần, ví dụ:

A= [1, 2, 3, 3, 4, 4, 4, 5, 6, 6]

Cho trước giá trị K, cần tìm ra vùng chỉ số gồm các phần tử bằng K. Chương trình cần trả về hai chỉ số start, end là vị trí bắt đầu và kết thúc gồm toàn các giá trị K. Nếu không tìm thấy K thì phải trả về -1, -1.

Trong ví dụ trên, nếu K = 4 thì cần trả về hai chỉ số 4, 6.

Lời giải:

Thực hiện các bước sau:

1. Tìm phần tử giữa của dãy.

2. Nếu giá trị ở vị trí giữa lớn hơn K, ta tiếp tục tìm kiếm trong nửa đầu của dãy (bên trái phần tử giữa).

3. Nếu giá trị ở vị trí giữa nhỏ hơn K, ta tiếp tục tìm kiếm trong nửa sau của dãy (bên phải phần tử giữa).

4. Nếu giá trị ở vị trí giữa bằng K, ta tiến hành tìm vị trí bắt đầu và kết thúc của đoạn chứa các phần tử bằng K bằng cách tiến hành tìm kiếm vị trí bắt đầu và kết thúc của các phần tử liên tiếp bằng K từ phải sang trái và từ trái sang phải. Khi tìm được hai vị trí này, ta sẽ trả về start và end.

5. Nếu không tìm thấy K trong dãy, ta trả về -1, -1.

Bài toán tìm vùng chỉ số của dãy đã sắp xếp