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ử

243

Với giải Vận dụng trang 30 Chuyên đề Tin học 11 Cánh diều chi tiết trong Bài 1: Ý tưởng 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:

Giải bài tập Chuyên đề Tin học 11 Bài 1: Ý tưởng chia để trị

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.

Lời giả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].

Đánh giá

0

0 đánh giá