数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找数组中是否存在一个元素的值等于数组总和的一半
在这个问题中，我们给定一个排序的唯一值的数组 arr。我们的任务是查找数组中是否存在一个元素的值等于数组总和的一半。
问题描述：对于数组 arr[]，我们需要在数组中找到一个元素 x，使得数组所有元素的总和等于 2*X。
让我们举个例子来理解这个问题，
输入：arr[] = {2, 4, 5, 6, 7}
输出：否
解释：
总和 = 2 + 4 + 5 + 6 + 7 = 24
未找到元素。
解决方案：
为了解决这个问题，我们只需要找到一个元素，该元素是数组所有元素总和的一半。
算法
步骤 1：找到数组所有元素的总和。
步骤 2：如果总和为奇数，则返回 -1。
步骤 3：如果总和为偶数，则找到元素 x，使得 x*2 = 总和。
步骤 4：如果找到元素，则返回 1。
步骤 5：如果未找到元素，则返回 -1。
为了搜索元素，我们可以使用二分查找算法，因为它已排序。
程序说明我们解决方案的工作原理，
示例
#include <iostream>
using namespace std;
int checkForElement(int array[], int n) {
int arrSum = 0;
for (int i = 0; i < n; i++)
arrSum += array[i];
if (arrSum % 2)
return -1;
int start = 0;
int end = n - 1;
while (start <= end)
{
int mid = start + (end - start) / 2;
if ( ( 2 * array[mid] ) == arrSum)
return array[mid];
else if (( 2 * array[mid] ) > arrSum)
end = mid - 1;
else
start = mid + 1;
}
return -1;
}
int main() {
int array[] = { 4, 5, 6, 7, 9 };
int n = sizeof(array) / sizeof(array[0]);
int x = checkForElement(array, n);
if(x != -1)
cout<<"Element found, value is "<<x;
else
cout<<"Element not found!";
return 0;
}输出 -
Element not found!
更新于： 2021年1月22日
157 次浏览
广告