Two Sum 2

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number, where index1 must be less than index2. Both index1 and index2 are not zero-based.

Problem from LeetCode



In [108]:

    
# Input
nums = [1,2,3,4,9,56,90]
target = 8



In [109]:

    
def binary_search(nums, target):
    left = 0
    right = len(nums) - 1
    middle = (left + right) // 2
    while left <= right:
        if nums[middle] == target:
            return middle
        elif target < nums[middle]:
            right = middle - 1
            middle = (left + right) // 2
        else:
            left = middle + 1 
            middle = (left + right) // 2
    return -1



In [110]:

    
def two_sum_2(nums, target):
    for i in range(len(nums)):
        remain = target - nums[i]
        result = binary_search(nums, remain)
        if result != -1 and result != i:
            return [i+1, result+1]  
two_sum_2(nums, target)



In [111]:

    
# Testing
for i, target in enumerate(nums):
    y = binary_search(nums, target)
    if y != i:
        print("Ooops, this should match, but doesn't. Index is", y, i, target)