資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告