在这个问题中，我们得到一个由 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 = 0; i--) {
if (P + (1
