C++二分查找A-B的问题案例

题目描述

同学们都还记得A+B问题吧，今天我们同样来个简单的A−B问题吧！

给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入描述

输入共两行。

第一行，两个正整数 N,C。

第二行，N 个正整数，作为要求处理的那串数。

输出描述

一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。

用例输入

4 1
1 1 2 3

用例输出

3

解决方法

这个问题可以通过使用二分查找来解决。首先，我们对输入的数列进行排序，然后遍历每一个数，在排序后的数列中寻找与当前数相差为C的数字。这样可以在O(NlogN)的时间复杂度内解决问题。

以下是相应的C++代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int count = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            count++;
            int i = mid - 1;
            while (i >= 0 && arr[i] == target) {
                count++;
                i--;
            }
            i = mid + 1;
            while (i < arr.size() && arr[i] == target) {
                count++;
                i++;
            }
            break;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return count;
}

int main() {
    int N, C;
    cin >> N >> C;

    vector<int> numbers(N);
    for (int i = 0; i < N; i++) {
        cin >> numbers[i];
    }

    sort(numbers.begin(), numbers.end());

    int count = 0;
    for (int i = 0; i < N; i++) {
        int target = numbers[i] - C;
        count += binarySearch(numbers, target);
    }

    cout << count << endl;

    return 0;
}

在这段代码中，我们首先输入正整数 N 和 C，表示数列长度和目标差值。然后输入N个正整数作为数列。接下来，我们对数列进行排序，然后使用二分查找找到与当前数相差为C的数字，并统计满足条件的数对个数，并最终输出结果。

运行结果