从小于O（n）的排序数组中查找唯一数字

从小于O（n）的排序数组中查找唯一数字

分而治之 ：

• 查看排序序列的第一个和最后一个元素（初始序列为

  data[0]..data[data.length-1]

  ）。
• 如果两者相等，则序列中的唯一元素是第一个（无论序列有多长）。
• 如果不同，则划分序列并为每个子序列重复。

一般情况下解决 O（log（n）） ，仅在最坏情况下解决O（n）（当每个元素不同时）。

Java代码：

public static List<Integer> findUniqueNumbers(int[] data) {    List<Integer> result = new linkedList<Integer>();    findUniqueNumbers(data, 0, data.length - 1, result, false);    return result;}private static void findUniqueNumbers(int[] data, int i1, int i2, List<Integer> result, boolean skipFirst) {    int a = data[i1];    int b = data[i2];    // homogenous sequence a...a    if (a == b) {        if (!skipFirst) { result.add(a);        }    }    else {        //divide & conquer        int i3 = (i1 + i2) / 2;        findUniqueNumbers(data, i1, i3, result, skipFirst);        findUniqueNumbers(data, i3 + 1, i2, result, data[i3] == data[i3 + 1]);    }}