Bạn An đã nghĩ ra thuật toán tìm kiếm nhị phân bằng đệ quy theo cách khác như sau

Vận dụng 3 trang 15 Chuyên đề Tin học 11: Bạn An đã nghĩ ra thuật toán tìm kiếm nhị phân bằng đệ quy theo cách khác như sau:

a) Chương trình của bạn An có đúng không?

b) Trong chương trình trên, phần cơ sở là những lệnh nào?

Trả lời

a) Chương trình của An đúng.

b) Phần cơ sở của đoạn lệnh trên là việc kiểm tra điều kiện kết thúc đệ quy, nếu left==right và A[left] == K thì trả về giá trị left, ngược lai nếu A[left] !=K thì trả về -1. Nếu không, tiếp tục tìm kiếm bằng cách tính giá trị mid ở giữa low và high, kiểm tra nó có bằng x hay không, nếu có thì trả về mid, nếu không thì tiếp tục tìm kiếm trong phần bên trái nếu x nhỏ hơn giá trị ở vị trí mid, hoặc phía bên phải nếu x lớn hơn giá trị ở vị trí mid. Quá trình đệ quy này sẽ tiếp tục cho đến khi tìm thấy giá trị x hoặc không tìm thấy và trả về -1.