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
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.
Giải Chuyên đề Tin 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị - Kết nối tri thức
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.
Lời giải bài tập Chuyên đề Tin 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị hay, chi tiết khác: