# 二分查找 – 数组中的重复元素

go评论62阅读模式

Binary-search with duplicate elements in array

# 问题

``````private static int findDuplicate(int array[]) {
int low = 0;
int high = array.length - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = array[mid];
if (midVal == mid)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
``````

``````[1,1,2,2,3,3,4,5,5]
``````

``````[1,1,2,2,3,4,4,5,5,6,6]
``````

``````[1,1,2,7,7,9,9]
``````

I want find if there is a single element in a list of duplicate elements.

For this code

``````private static int findDuplicate(int array[]) {
int low = 0;
int high = array.length - 1;

while (low &lt;= high) {
int mid = (low + high) &gt;&gt;&gt; 1;
int midVal = array[mid];
if (midVal == mid)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
``````

It find the duplicate number but I want to find only the single number
in the duplicate and sorted array.

For example, given this int[] input:

``````[1,1,2,2,3,3,4,5,5]
``````

Output would be '4'.

Or this int[] input:

``````[1,1,2,2,3,4,4,5,5,6,6]
``````

Output would be '3'.

In this int[] input:

``````[1,1,2,7,7,9,9]
``````

Output would be '2'.

I'm working in Java now but any language or psuedo-code is fine.

I know the obvious traversal at O(n) linear time, but I'm trying to see if this is possible via binary search at O(log n) time.

The elements are sorted and only duplicate twice!
I know the way with simple loop but I want to do it by binary search.

# 答案1

``````(1 1) (2 2) (3 3) <i><b>(4 5) (5 6) (6 7) (7 8) (8)</b></i>
``````

Consider each pair of 2 consecutive elements: (the pairs with 2 elements different are highlighted) (note that there's a stray element at the end)

<pre><code>(1 1) (2 2) (3 3) <i><b>(4 5) (5 6) (6 7) (7 8) (8)</b></i>
</code></pre>

Observe that the only non-duplicated element will make the corresponding pair and all the later pairs have different values, the pairs before that have the same value.

So just binary search for the index of the different pair.

This algorithm also don't require that the list is sorted, only that there's exactly one element which appears once, and all other elements appear twice, in consecutive indices.

Special case: if the last element is the unique one, then all the pairs will have equal values.

# 答案2

（0,1），
（2,3），
（4,5）
（6,7）

``````low = 0，high = arr.length - 1

while low <= high:
mid = (low + high) / 2
if mid == 0 || mid == arr.length - 1 || arr[mid] != arr[mid-1] and arr[mid] != arr[mid + 1]: // 如果它们是边界值，或者左右两边的值都不同，那么完成
return arr[mid]
if(mid % 2 == 0):
if arr[mid + 1] != arr[mid]: // 由于偶数索引具有对称性，因此与下一个索引进行检查
high = mid
else:
low = mid + 2
else:
if arr[mid - 1] != arr[mid]: // 由于奇数索引具有对称性，因此与前一个索引进行检查
high = mid
else:
low = mid + 1

return -1
``````

Every pair of same values will be like below in terms of indices:

``````(0,1),
(2,3),
(4,5)
(6,7)
``````

etc. You can clearly see that if index is even, check with next element for similarity. If index is odd, you can check with previous value for similarity.
If this symmetry is broken, you can move towards left side or if everything is ok, keep moving right.

Pseudocode(not tested):

``````low = 0,high = arr.length - 1

while low &lt;= high:
mid = (low + high) / 2
if mid == 0 || mid == arr.length - 1 || arr[mid] != arr[mid-1] and arr[mid] != arr[mid + 1]: // if they are corner values or both left and right values are different, you are done
return arr[mid]
if(mid % 2 == 0):
if arr[mid + 1] != arr[mid]: // check with next index since even for symmetry
high = mid
else:
low = mid + 2
else:
if arr[mid - 1] != arr[mid]: // check with prev index since odd for symmetry
high = mid
else:
low = mid + 1

return -1
``````

• 本文由 发表于 2020年10月5日 21:13:13
• 转载请务必保留本文链接：https://go.coder-hub.com/64209344.html
• algorithm
• binary-search
• java

go 63

go 69

go 69

go 53