在C ++中的连续数字排序数组中查找丢失的元素
概念
对于n个不同整数的给定arrayarray[]，将元素按升序顺序放置，其中一个缺少元素。我们的任务是确定缺少的元素。
输入值
array[] = {1, 2, 3, 4, 5, 6, 7, 9}输出结果
8
输入值
array[] = {-4, -2, -1, 0, 1, 2}输出结果
-3
输入值
array[] = {1, 2, 3, 4}输出结果
-1
没有元素丢失。
方法
原则
寻找不一致性：根据此原理，每个元素及其索引之间的差必须为array[0]。
例，
A[]={1,2,3,4,5}->一致
B[]={201，202，203，204}->一致
C[]={1,2,3,5,6}->与C[3]–3！=C[0]不一致，即5–3！=1
确定不一致有助于每次仅以O(logN)扫描数组的一半。
算法
确定中间元素并验证其是否一致。
如果中间元素是一致的，则验证中间元素与其下一个元素之间的差是否大于1，即验证array[mid+1]–array[mid]>1
如果是，则array[mid]+1是缺少的元素。
否则，我们必须从中间元素扫描右边的一半数组，然后跳到步骤1。
如果中间元素不一致，则验证中间元素与其前一个元素之间的差是否大于1，即验证array[mid]–array[mid–1]>1
如果是，则array[mid]–1是缺少的元素。
否则，我们必须扫描中间元素的左半部分数组，然后跳至步骤1。
示例
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
//显示函数以返回缺少的元素
int findMissing(int array[], int n1){
int low = 0, high = n1 - 1;
int mid1;
while (high > low){
mid1 = low + (high - low) / 2;
//验证中间元素是否一致
if (array[mid1] - mid1 == array[0]){
//在这里，直到中间元素没有矛盾
//当缺少元素在
//中间元素
if (array[mid1 + 1] - array[mid1] > 1)
return array[mid1] + 1;
else{
//往右走
low = mid1 + 1;
}
}
else{
//在这里发现不一致
//当缺少元素在之前
//中间元素
if (array[mid1] - array[mid1 - 1] > 1)
return array[mid1] - 1;
else{
//向左走
high = mid1 - 1;
}
}
}
//在这里，找不到丢失的元素
return -1;
}
//驱动程式码
int main(){
int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
int n1 = sizeof(array)/sizeof(array[0]);
cout <<"缺少的元素：" <<(findMissing(array, n1));
}输出结果
缺少的元素：-7