# 167. Two Sum II - Input Array Is Sorted

題目：<https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/>

解法一：使用 two pointers 方法，由於 input array 已經排序好，left pointer 取第一個，即最小值，right pointer 取最後一個，即最大值，若相加後大於目標值，則 right pointer 往左移，取得小一點的值，反之，若相加後小於目標值，left pointer 往右移，取得大一點的值，反覆此步驟直到相加等於目標值為止。

Python3：

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        idx1 = 0
        idx2 = len(numbers) - 1
        while idx1 < idx2:
            num = numbers[idx1] + numbers[idx2]
            if num == target:
                break
            elif num > target:
                idx2 -= 1
            else:
                idx1 += 1
        return [idx1 + 1, idx2 + 1]

if __name__ == '__main__':
    numbers = [2, 7, 11, 15]
    target = 9

    ans = Solution().twoSum(numbers, target)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int idx1 = 0, idx2 = numbersSize - 1;
    while (idx1 < idx2) {
        int num = numbers[idx1] + numbers[idx2];
        if (num == target)
            break;
        else if (num > target)
            idx2--;
        else
            idx1++;
    }
    *returnSize = 2;
    int* output = (int*)malloc(sizeof(int) * 2);
    output[0] = idx1 + 1;
    output[1] = idx2 + 1;
    return output;
}

int main() {
    int numbers[] = {2, 7, 11, 15};
    int numbersSize = sizeof(numbers) / sizeof(numbers[0]);
    int target = 9;
    
    int returnSize;
    int* ans = twoSum(numbers, numbersSize, target, &returnSize);
    for (int i = 0; i < returnSize; i++)
        printf("%d\n", ans[i]);
    return 0;
}

解法二：二元搜尋法，從頭開始搜尋，假設第一個元素位置在 idx1，接著從 idx1 之後的陣列中搜尋是否有值為 target - numbers[idx1] 的元素，若有的話就輸出結果，沒有的話將 idx1+1 再次搜尋。

Python3：

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        def binarySearch(arr, target):
            left = 0
            right = len(arr) - 1
            while left <= right:
                mid = (left + right) // 2
                if arr[mid] > target:
                    right = mid - 1
                elif arr[mid] < target:
                    left = mid + 1
                else:
                    return mid
            return ~left
        idx1 = 0
        idx2 = binarySearch(numbers[idx1+1:], target - numbers[idx1])
        while idx2 < 0:
            idx1 += 1
            idx2 = binarySearch(numbers[idx1+1:], target - numbers[idx1])
        return [idx1 + 1, idx1 + idx2 + 2]

if __name__ == '__main__':
    numbers = [1, 2, 3, 4, 4, 9, 56, 90]
    target = 8

    ans = Solution().twoSum(numbers, target)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>

int binarySearch(int* arr, int arrSize, int target) {
    int left = 0, right = arrSize - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] > target)
            right = mid - 1;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            return mid;
    }
    return ~left;
}

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
    int idx1 = 0;
    int idx2 = binarySearch(numbers + idx1 + 1, numbersSize - idx1 - 1, target - numbers[idx1]);
    while (idx2 < 0) {
        idx1++;
        idx2 = binarySearch(numbers + idx1 + 1, numbersSize - idx1 - 1, target - numbers[idx1]);
    }
    *returnSize = 2;
    int* output = (int*)malloc(sizeof(int) * 2);
    output[0] = idx1 + 1;
    output[1] = idx1 + idx2 + 2;
    return output;
}

int main() {
    int numbers[] = {1, 2, 3, 4, 4, 9, 56, 90};
    int numbersSize = sizeof(numbers) / sizeof(numbers[0]);
    int target = 8;
    
    int returnSize;
    int* ans = twoSum(numbers, numbersSize, target, &returnSize);
    for (int i = 0; i < returnSize; i++)
        printf("%d\n", ans[i]);
    return 0;
}

###### tags: `leetcode` `array` `two pointers` `binary search`