使用 C++ 中的二进制提升法，在 N 个数字的前缀和中查找第一个大于或等于 X 的元素
c++server side programmingprogramming更新于 2025/5/31 9:07:17
在此问题中，我们给出一个由 N 个数字和一个整数值 x 组成的数组 arr[]。我们的任务是创建一个程序，使用二进制提升法查找 N 个数字的前缀和中第一个大于或等于 X 的元素。
数组元素的前缀和是一个数组，其每个元素都是初始数组中该索引之前所有元素的总和。
示例 − array[] = {5, 2, 9, 4, 1
prefixSumArray[] = {5, 7, 16, 20, 21
让我们举一个例子来理解这个问题，
输入:arr[] = {5, 2, 9, 4, 1}, X = 19
输出:3
解决方法
在这里，我们将使用二元提升的概念来解决问题。二元提升是将给定数字的值增加 2 的幂(通过翻转位来完成)，范围从 0 到 N。
我们将考虑一个类似于提升二叉树的概念，我们将在其中找到"P"索引的初始值。通过翻转位来增加该值，确保该值不大于 X。现在，我们将考虑提升以及该位置"P"。
为此，我们将开始翻转数字的位，以使第 i 位翻转不会使总和大于 X。现在，我们有两种基于"P"值减去"P"的情况
目标位置位于"位置 + 2^i"和"位置 + 2^(i+1)"之间，其中第 i 个提升增加了值。或者，目标位置位于"位置"之间和"position + 2^i"。
使用这个我们将考虑索引位置。
示例
程序来说明我们的解决方案的工作原理
#include <iostream>
#include <math.h>
using namespace std;
void generatePrefixSum(int arr[], int prefSum[], int n){
prefSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefSum[i] = prefSum[i - 1] + arr[i];
}
int findPreSumIndexBL(int prefSum[], int n, int x){
int P = 0;
int LOGN = log2(n);
if (x <= prefSum[0])
return 0;
for (int i = LOGN; i >= 0; i--) {
if (P + (1 << i) < n &&
prefSum[P + (1 << i)] < x) {
P += (1 << i);
}
}
return P + 1;
}
int main(){
int arr[] = { 5, 2, 9, 4, 1 };
int X = 19;
int n = sizeof(arr) / sizeof(arr[0]);
int prefSum[n] = { 0 };
generatePrefixSum(arr, prefSum, n);
cout<<"数组中大于给定数字的第一个元素的索引是 ";
cout<<findPreSumIndexBL(prefSum, n, X);
return 0;
}
输出
数组中大于给定数字的第一个元素的索引是 3
