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

Giải Chuyên đề Tin học 11 Cánh diều 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].