Em hãy viết chương trình tìm kiếm nhị phân giá trị x trong dãy số không giảm A có n phân tử, các

Vận dụng trang 30 Chuyên đề Tin học 11: Em hãy viết chương trình tìm kiếm nhị phân giá trị x trong dãy số không giảm A có n phân tử, các phần tử có thể trùng nhau: kết quả là hiện thị chỉ số nhỏ nhất 7 sao cho Ai = x hoặc hiển thị thông báo không tìm thấy x.

Trả lời

Do tính chất mảng đã sắp xếp, công việc tìm kiếm phần tử x có thể triển khai như sau:

1. Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:

2. Nếu phần tử arr[mid] = x. Kết luận và thoát chương trình.

3. Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].

4. Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].

Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Cánh diều hay, chi tiết khác:

Bài 3: Thực hành thiết kế thuật toán đệ quy

Bài 4: Thực hành tổng hợp thiết kế thuật toán đệ quy

Bài 1: Ý tưởng chia để trị

Bài 2: Kĩ thuật đệ quy trong chia để trị

Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy

Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn

Câu hỏi cùng chủ đề

Xem tất cả