Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần, hãy tìm một vị trí thứ i

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

Vận dụng 2 trang 39 Chuyên đề Tin học 11: Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần, hãy tìm một vị trí thứ i trong dãy sao cho phần tử thứ i có giá trị bằng i.

Lời giải:

Để tìm vị trí thứ i trong dãy số sao cho phần tử thứ i có giá trị bằng i, ta có thể sử dụng phương pháp chia để trị như sau:

1. Tìm giá trị trung bình của left và right: mid = (left + right) // 2

2. Nếu giá trị tại vị trí mid bằng mid, tức là A[mid] == mid, thì trả về mid

3. Nếu giá trị tại vị trí mid lớn hơn mid, tức là A[mid] > mid, thì tiếp tục tìm vị trí thích hợp trong đoạn từ left đến mid-1

4. Nếu giá trị tại vị trí mid nhỏ hơn mid, tức là A[mid] < mid, thì tiếp tục tìm vị trí thích hợp trong đoạn từ mid+1 đến right

5. Nếu không tìm được vị trí thích hợp nào, tức là left > right, thì trả về -1

Ví dụ:

Kết quả sẽ là "Vị trí thích hợp là: 3", tức là phần tử thứ 3 trong dãy A có giá trị bằng 3.