# Another Binary Search idea

• This idea is to use alternative binary search rather than simply search the target - number[i] each time.
Although the worst case will also result in O(n) time complexity, but the overall performance is much better if the input is very sparse.

``````var twoSum = function(numbers, target) {

var i=0, j=numbers.length-1;
var sum;

while (i<j){
//move j using binary search to find largest nums[j] that nums[i] + nums[j] <= target
var tmpi = i+1, tmpj = j;
var first = numbers[i];
while (tmpi <= tmpj){
var m = Math.floor((tmpi+tmpj)/2);
if (numbers[m] + first === target){
return [i+1, m+1];
}
else if (numbers[m] + first > target){
tmpj = m-1;
}
else {
tmpi = m+1;
}
}
j = tmpj;

//move i using binary search to find smallest nums[i] that nums[i] + nums[j] >= target
var last = numbers[j];
tmpi = i+1, tmpj = j-1;
while (tmpi <= tmpj){
var m = Math.floor((tmpi+tmpj)/2);
if (numbers[m] + last === target){
return [m+1, j+1];
}
else if (numbers[m] + last > target){
tmpj = m-1;
}
else {
tmpi = m+1;
}
}
i = tmpi;
}
};``````

• Would you mind explain why worse case O(n)? I have the same idea, but don't know what the time complexity is... Thanks.

• Please consider this case: 1, 3, 5, 7, 9, 11, 13 .... n+1, n+2, n+3, n+5, ... 2n-1, 2n+1 and your target is 2n+3, it will cost you O(n) binary search to reach the middle for n+1 and n+2

• Ah! I see, thanks for your explanation.

• I have the same idea, but I think the worse case is O(nlogn) because we need n times binary search and each time the range is only subtract by one.

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