Hãy đếm xem trong dãy số trên có bao nhiêu cặp thoả mãn ai + aj = X (i < j) (sử dụng tìm kiếm nhị phân, c++)

Để giải bài toán này, ta có thể sử dụng phương pháp tìm kiếm nhị phân để tìm các cặp số thoả mãn điều kiện ai + aj = X.

Bước 1: Sắp xếp dãy số a theo thứ tự tăng dần.

Bước 2: Duyệt qua từng phần tử ai trong dãy số a.

Bước 3: Tìm kiếm nhị phân phần tử X - ai trong đoạn từ i+1 đến N-1 của dãy số a.

Bước 4: Nếu tìm thấy phần tử X - ai, tăng biến đếm lên 1.

Bước 5: Lặp lại từ bước 2 đến bước 4 cho tất cả các phần tử trong dãy số a.

Bước 6: Trả về giá trị biến đếm là số cặp thoả mãn điều kiện ai + aj = X.

Dưới đây là mã giả của thuật toán:

```cpp
int countPairs(int N, int a[], int X) {
// Sắp xếp dãy số a theo thứ tự tăng dần
sort(a, a + N);

int count = 0;

// Duyệt qua từng phần tử ai trong dãy số a
for (int i = 0; i < N; i++) {
// Tìm kiếm nhị phân phần tử X - ai trong đoạn từ i+1 đến N-1 của dãy số a
int left = i + 1;
int right = N - 1;

while (left <= right) {
int mid = (left + right) / 2;

if (a[mid] == X - a[i]) {
count++;
break;
} else if (a[mid] < X - a[i]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}

return count;
}
```

Độ phức tạp của thuật toán này là O(N log N) do sắp xếp dãy số a và tìm kiếm nhị phân.