在未排序的数组中查找唯一数字时出现问题

Question

一种方法，它接收一个未排序的数组，该数组由成对的相邻相等数字以及一个没有对的数字组成。例如

int [] a = {6,6,18,18,-4,-4,12,9,9};
int [] c = {8,-7,-7,3,3,0,0,10,10,5,5,4,4};

代码必须返回索引和数字本身。

现在的问题是关于时间复杂性，我知道O(logn(可以解决这个问题，但我的代码只起了一半的作用：

public static int findSingle (int [] a) {
int high = a.length-1;
int low = 0;
int mid = 0;
int found = 0;
mid = ((high-low)/2);
while (mid >= 1) {
if (a[mid] != a[mid-1])
low = mid +1;
mid =((high - low)/2);
if (mid == 1)
found = a[mid];
if (a[mid] == a[mid-1])
high = mid-1;
mid = ((high - low)/2);
}
return found;
}

现在给定这个数组：

int [] d = {8,8,-7,3,3,0,0,10,10,5,5,4,4};

它说数字在第8个元素中，这显然不是真的，在一些数组中它也会出错。怎么了？

编辑：我注意到我应该分配"；中间"；高+低/2，但这两种方式都不能解决问题。

Answer 1

您正走在正确的轨道上，但您的代码存在一些问题。

while (mid >= 1)

为什么mid小于或等于1是你的退出条件？您希望您的退出条件是当您找到您的值时，该值可以在数组中的任何位置，而不仅仅是在开头。我将把退出条件更改为基于high和low，就像在普通的二进制搜索中一样。

mid = ((high-low)/2);

首先，这个公式没有找到high和low中间的数字。这应该是((high+low)/2)。此外，这些列表的性质使得保持mid的奇偶性一致非常重要。即使在设置了mid时添加mid += mid%2;，我也要确保mid保持不变。

low = mid +1;
...
high = mid-1;

同样，high和low的奇偶性是非常重要的。两者应始终保持平衡。我们知道mid是偶数，所以high和low不应该被mid偏移+/-1。

if (mid == 1)
found = a[mid];

这是代码中最大的问题。首先，你是想找到单个数字的索引还是单个数字的值？您说您正在查找索引，但您的代码正在查找a[mid]，这是一个值。我下面的代码可以找到索引，但这可以很容易地更改。其次，只有当mid为1时，才执行此操作。这意味着您的代码将始终返回0或a[1]。

还有其他几个注意事项。没有理由为每个循环设置两次mid并检查a[mid] != a[mid-1]和a[mid] == a[mid-1]。相反，将mid设置为每个循环一次，检查其中一个条件，然后使用if/else。此外，没有理由使用found。相反，只要在循环退出时使用high或low的值，现在它已经正确退出了。

最终代码：

public static int findSingle (int [] a) {
int high = a.length-1;
int low = 0;
int mid = 0;
while (high != low) {
mid = ((high + low) / 2);
mid += mid%2;
if (a[mid] != a[mid-1])
low = mid;
else
high = mid - 2;
}
return high;
}

我还没有对此进行彻底的测试，但从我查看的少数测试案例来看，它似乎有效。

编辑：

原来有一个bug(感谢Alex Rudenko(。固定版本：

public static int findSingle (int [] a) {
int high = a.length-1;
int low = 0;
int mid = 0;
while (high != low) {
mid = ((high + low) / 2);
mid -= mid%2;
if (a[mid] == a[mid+1])
low = mid + 2;
else
high = mid;
}
return high;
}