在这个问题中，我们得到一个由 N 个数字和一个整数值 x 组成的数组 arr[]。我们的任务是创建一个程序，使用二进制提升在 N 个数字的前缀和中查找大于或等于 X 的第一个元素。
前缀和数组元素的强>是一个数组，其每个元素是初始数组中直到该索引为止的所有元素的总和。
示例 - array[] = {5, 2, 9, 4, 1 }
prefixSumArray[] = {5, 7, 16, 20, 21}
让我们举个例子来理解这个问题，
Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3登录后复制
解决方案
在这里，我们将使用二元提升的概念来解决问题。二元提升是将给定数字的值增加 2 的幂（通过翻转位完成），范围从 0 到 N。
我们将考虑一个类似于提升二叉树的概念，我们将在其中找到“P”指数的初始值。这是通过翻转位来增加的，确保该值不大于 X。现在，我们将考虑这个位置“P”的升力。
为此，我们将开始翻转数字的位，例如第 i 位翻转不会使总和大于 X。现在，根据 'P' 的值，我们有两种情况 -
目标位置位于 'position + 2 之间^i”和“位置 + 2^(i+1)”，其中第 i 次提升增加了值。或者，目标位置位于“position”和“position + 2^i”之间。
使用此我们将考虑索引位置。
示例
说明我们解决方案工作原理的程序
#include
#include
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<<"The index of first elements of the array greater than the given number is ";
cout<登录后复制
输出
The index of first elements of the array greater than the given number is 3
登录后复制
위 내용은 使用C++中的二进制提升，在N个数字的前缀和中找到第一个大于或等于X的元素의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
