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ị
20
22/07/2024
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].
