Epoch

Question 

  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.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that you returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

題意

  像是培養鍛鍊程式設計的邏輯腦一書中提到的抽籤問題，要找出兩個數字和等於他想找的數字。

想法

  最開始的想法就是用兩個 for 迴圈依序檢驗，但這樣複雜度為 n^2，他一開始即是排好序的，不就說明可以使用 binary search 嗎? 於是先把欲求的和，扣掉任一數字後，再從剩下的數字中，找有沒有剛剛的差，若找到，就是這兩個 index 可以合成，在找差的時候，可以使用 binary search，原本可能要找 n-1 次，這樣可以找 logn 次，複雜度從 n^2 降為 nlogn。

code

int binary_search(int* numbers, int numbersSize, int x) {
    int l=0, r=numbersSize;
    
    while(r-l > 0) {
        int i = (l + r) / 2;
        if(numbers[i] == x) {
            return i+1;
        }
        else if(numbers[i] < x) l = i + 1;
        else r = i;
    }
    return 0;
}
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int i;
    int* idx;
    idx = malloc(sizeof(int)*2);
    for(i=0; i<numbersSize; i++) {
        idx[0] = i+1;
        idx[1] = binary_search(numbers, numbersSize, target-numbers[i]);
        if(idx[1]) {
            *returnSize = 2;
            return idx; 
        }
    }
    return false;
}

以上 binary search 是使用迴圈的辦法，還想嘗試看看遞迴的作法。