# Is there a logN solution?

• I saw some binary search solutions but in fact they are worst case linear or even nlogn. Is there a 100% logN (i.e. worst case logN) solution?

• No, you can't beat O(n).

Consider `numbers = {2, 4, 6, 8, ..., 98, 100}` and `target = 102`. There are 50 solution pairs. Now increase one of the numbers by 1 and also increase the target to 103. Then there's exactly one solution pair. To find it, you need to find the increased number, and it could be anywhere. Whatever strategy you use, you might get unlucky and find it only after having looked at all other numbers.

• This post is deleted!

• @StefanPochmann Aha, nice to see you again.

Thank you for your explanation! Fully understood

• Please check my post where I illustrated my idea of Binary Search which can achieve O(logN) in average case but it's O(N) in the worst case (actually even slower) and also it's getting stack overflow with huge input. However I think the idea is right.
The subject of my post is "O(log N) Average Case Binary Search Solution Idea - Failing Large Input Test Case"

• @rmn Can't you just link to it?

• @rmn Would appreciate it if you can send a link to it. There is a lot of posts on your page so...

Appreciate it!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.