我知道这个问题被问了很多次然而，在StackOverflow上的所有相关帖子中，我仍然没有找到确定的答案你能帮忙吗？
我的问题是，对于这样的问题，O（log n）解是否存在？为了使问题更清楚，我们可以分别研究两个案例：案例（1）a没有重复，案例（2）a有重复元素。
我听说基于二进制搜索的解决方案似乎能够实现O（log n），但不明白它是如何实现的这里n是A中元素的数目。
最佳答案
假设元素i对于每个位置都有值2i，除了一个位置有值2i+1。
如果目标是一个值2n+1，那么我们必须测试每一对i和n-i，直到找到2i+1的位置。
因此，在这两种情况下都不可能做得比o（n）好。