0 ms Binary Search Solution

• This solution combines two pointer with binary search ,i think it's O(log n) complexity.

``````public class Solution {
//high：寻找比target小，但是其右边比target大的坐标
//low：寻找比target大，但是左边比target小的坐标
public int[] twoSum(int[] numbers, int target) {
int low = 0;
int high = numbers.length-1;
while(low < high) {
if((numbers[low] + numbers[high]) > target) {
int start = low+1;
int end = high;
while(start < end) {
int mid = (start+end)/2;
if((numbers[low] + numbers[mid]) > target) {
end = mid-1;
}else if((numbers[low] + numbers[mid]) < target) {
start = mid+1;
}else{
end = mid;
break;
}
}
if((numbers[low] + numbers[end]) > target) end--;
high = end;
}else if((numbers[low] + numbers[high]) < target) {
int start = low;
int end = high-1;
while(start < end) {
int mid = (start+end)/2;
if((numbers[high] + numbers[mid]) > target) {
end = mid-1;
}else if((numbers[high] + numbers[mid]) < target) {
start = mid+1;
}else{
end = mid;
break;
}
}
if((numbers[end] + numbers[high]) < target) end++;
low = end;
}else{
break;
}
}
return new int[]{low+1, high+1};
}
}``````

• O( (log n) ^ 2)?

• The worst case O(n log n),
numbers = [1 3 5 7 9 ..... 47 49 50 52 54 .... 94 96 98], target = 100

• Your solution does not work with negative ints in the input. I do not believe you can use a binary search on this problem unless you are told there will only be positives (which we have not been given in the instructions)

INPUT: [-12,3,4,12]
12

Output:
[3,3]

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