0 ms Binary Search Solution


  • 2

    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};
        }
    }

  • 0
    G

    O( (log n) ^ 2)?


  • 0
    F

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


  • 0
    D

    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]


Log in to reply
 

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