这个问题的答案是O(n),这就是原因.
让我们首先总结一下我们所获得的知识:
问题是搜索只出现一次的那一项的时间增长是多少？
数组的排序属性,我们可以使用它来加速搜索项目吗？是的,不.
首先,由于数组没有按属性排序,我们必须使用它来查找项目(只有一次出现),然后我们就不能在这方面使用sorted属性.这意味着优化的搜索算法,例如二进制搜索,已经完成.
但是,我们知道如果数组已排序,则具有相同值的所有项将组合在一起.这意味着当我们第一次看到我们看到的项目时,我们只需要将它与下面的项目进行比较.如果它不同,我们找到了我们正在寻找的物品.
"第一次看到"很重要,否则我们会选择第一个值,因为两个项目之间存在两个项目不同的边界.
所以我们必须从数组的一端移动到另一端,并将每个项目与下面的项目进行比较,这是一个O(n)操作.
基本上,由于数组没有按我们正在查看的属性排序,我们回到线性搜索.