# 4ms Binary Search O(n*log(n))

• The quick idea is to use Binary Search for a complement number.
There is another idea is to use 2 runners until desired sum is found.

``````vector<int> twoSum(vector<int>& numbers, int target)
{
// predefine result if no items found
vector<int> res(2, -1);

for (int ndxFirst=0; ndxFirst<(numbers.size()-1); ++ndxFirst)
{
// skip same numbers if sum not equal to target
if (numbers[ndxFirst] == numbers[ndxFirst+1])
{
if ((numbers[ndxFirst] + numbers[ndxFirst+1]) == target)
{
res[0] = ndxFirst+1;
res[1] = ndxFirst+2;
break;
}
else
{
continue;
}

}

// if first number is bigger than target - you wont find second anyway.
if (numbers[ndxFirst] > target)
{
break;
}

// search for complement number starting from ndxFisrt+!
int ndxSecond = binarySearch(numbers, ndxFirst+1, target-numbers[ndxFirst]);

// if complement number is found - store them into result and finish
if (ndxSecond != -1)
{
res[0] = ndxFirst+1;
res[1] = ndxSecond+1;
break;
}
}

return res;
}

int binarySearch(vector<int> &numbers, int ndxStart, int value)
{
int ndxEnd = numbers.size()-1;

while (ndxStart <= ndxEnd)
{
int ndxMiddle = (ndxEnd-ndxStart)/2 + ndxStart;

// if middle number is bigger than desired - search in the left partition
if (value < numbers[ndxMiddle])
ndxEnd = ndxMiddle-1;

// if middle number is smaller than desired - search in the right partition
else if (value > numbers[ndxMiddle])
ndxStart = ndxMiddle+1;

// else is when value and middle number are equal, which means we found it.
else
return ndxMiddle;
}

return -1;
}
``````

• your code needs 8ms in my submit

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