二进制搜索O（log n）算法在顺序列表中查找重复？

有没有人知道在序列号列表中找到重复的快于线性的算法？ 我现在在Java工作，但任何语言或伪代码都没问题。

例如，给定此int []输入：

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 8 | 9 

输出可以是指数或值’7’。

我知道O(n)线性时间的明显遍历，但我试图通过O(log n)时间的二进制搜索来确定这是否可行。

Answer 1

如果假设数字必须从0开始并且增加1，则可以将中间值与索引进行比较。 如果中间是相同的更高，如果中间不是，则降低。

这将为您提供二进制搜索时间O（log2 N）。 唯一的区别是您要与索引进行比较，而不是固定值。

---

 public static void main(String... args) { int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9}; int duplicate = findDuplicate(array); System.out.println(duplicate); } 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; } 

Answer 2

请注意，二进制搜索适用于排序列表。 因此，如果您有一个带有重复项的排序列表，则二进制搜索仅在您的副本相邻时才有用。 相邻的重要性是，您可以在找到的密钥的上一个和下一个位置测试密钥的存在。 尝试在未排序列表上使用二进制搜索的任何其他方式都会产生不正确的结果。

这里有一些代码来表明我的意思。

 import java.util.Arrays; public class Main { public static void main(String[] args) { int[] list = {1, 2, 3, 4, 5, 6, 7, 7, 8, 9 }; int key = 7; int result = Arrays.binarySearch(list, key); System.out.println(result); if( list[result+1] == key || list[result-1] == key ) System.out.println("yes we have a duplicate."); } } 

if为O（1）的比较我们保留了二进制搜索的O（logn）。

Answer 3

 public class DuplicateNumber { public int findDuplicateNumber(List numbers){ int highestNumber = numbers.size() - 1; int total = getSum(numbers); int duplicate = total - (highestNumber*(highestNumber+1)/2); return duplicate; } public int getSum(List numbers){ int sum = 0; for(int num:numbers){ sum += num; } return sum; } public static void main(String a[]){ List numbers = new ArrayList(); for(int i=1;i<30;i++){ numbers.add(i); } //add duplicate number into the list numbers.add(22); DuplicateNumber dn = new DuplicateNumber(); System.out.println("Duplicate Number: "+dn.findDuplicateNumber(numbers)); } }