Lời giải chi tiết:

Đầu tiên, các bạn cần khai báo kiểu dữ liệu của số \(n\) . Sau đó, các bạn dùng lệnh cin để nhập số n vừa khai báo ở trên. Tiếp theo, các bạn cần khai báo mảng \(a\) có kích thước \(n\) và dùng lệnh cin để nhập từng phần tử của mảng \(a\). Tiếp theo, khai báo kiểu dữ liệu của số nguyên \(q\) - thể hiện cho số lượng bố test. Cuối cùng các bạn hãy nhập đủ \(q\) số nguyên \(k\) (Gợi ý dùng vòng while để nhập)

Thuật toán

Bước 1: Để tìm số \(k\) lớn thứ mấy trong mảng. Ta cần sắp xếp mảng theo thứ tự tăng dần (gợi ý dùng thuật toán quicksort hoặc bubble sort)

Bước 2: Sau khi mảng đã được sắp xếp, ta sẽ sử dụng thuật toán tìm kiếm nhị phân để tìm vị trí của số \(k\) trong mảng. Chi tiết sẽ được viết ở các bước sau.

Bước 3: Tìm kiếm nhị phân:

• Đặt \(left = 0\), \(right = n-1\) (với \(n\) là số phần tử của mảng)
• Trong khi \(left <= right\):
  • Đặt \(mid = (left + right) / 2\)
  • Nếu \(a[mid] == k\), trả về \(mid + 1\)
  • Nếu \(a[mid] < k\), đặt \(left = mid + 1\)
  • Nếu \(a[mid] > k\), đặt \(right = mid - 1\)

Khi đó, ta sẽ trả về \(mid + 1\) (vị trí của số \(k\) trong mảng) cũng là đáp án của bài toán

Đăng ký khóa học https://www.facebook.com/clblaptrinhfullhouse

SĐT liên hệ: 0372229686

Youtube: CLB Lập Trình Full House

_Fullhouse Dev đồng hành trên từng dòng code_