---
tags: LeetCode
---

# 167. Two Sum II - Input array is sorted
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.

Note:
Your 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**.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

---
輸入範本如下

public class Solution {
        public int[] TwoSum(int[] numbers, int target)
        {            
        }
}

### 直覺想法
1. two index 去找.
- 使用兩個 index 去逼近 , 若找到的值太小 , left-- , 反之 right++

    248 ms	31.2 MB
    You are here!
    Your runtime beats 53.69 % of csharp submissions.
    public int[] TwoSum(int[] numbers, int target)
    {
        for (int left = 0, right = numbers.Length - 1; left < right;)
        {
            int value = numbers[left] + numbers[right];
            if (value == target)
            {
                return new int[] { left + 1, right + 1 };
            }
            else if (value < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        throw new Exception("not found");
    }

2. 二分搜尋法
- 使用二分搜尋逼近找解 ,
- 需要注意的是 **left + 1** 不能放入 left , 否則可能會找到 left , left 的答案.

244 ms	31.3 MB	
You are here!
Your runtime beats 71.98 % of csharp submissions.
public int[] TwoSum(int[] numbers, int target)
{
    for (int left = 0, right = numbers.Length - 1; left < right; left++)
    {
        int find = BinarySearch(numbers, left + 1, right, target - numbers[left]) ?? -1;
        if (find != -1)
        {
            return new int[] { left + 1, find + 1 };
        }
    }
    throw new Exception("not found");

    int? BinarySearch(int[] num, int l, int r, int find)
    {
        while (l <= r)
        {
            int index = (l + r) / 2;
            if (num[index] == find)
                return index;
            else if (num[index] < find)
                l = index + 1;
            else if (num[index] > find)
                r = index - 1;
        }
        return null;
    }
}

3. 一樣是二分搜尋
- 差別從兩個方向去逼近 , 避免解答在最右邊的位置處.

244 ms	31.1 MB
You are here!
Your runtime beats 71.98 % of csharp submissions.
public int[] TwoSum(int[] numbers, int target)
{
    int left = 0;
    int right = numbers.Length - 1;

    //使用二元搜尋法去尋找left以及right
    while (numbers[left] + numbers[right] != target)
    {
        if (numbers[left] + numbers[right] < target)
            left = BinarySearch(numbers, left + 1, right - 1, target - numbers[right]) ?? left + 1;
        else if (numbers[left] + numbers[right] > target)
            right = BinarySearch(numbers, left + 1, right - 1, target - numbers[left]) ?? right - 1;
    }
    return new int[] { left + 1, right + 1 };

    int? BinarySearch(int[] num, int l, int r, int find)
    {
        while (l <= r)
        {
            int index = (l + r) / 2;
            if (num[index] == find)
                return index;
            else if (num[index] < find)
                l = index + 1;
            else if (num[index] > find)
                r = index - 1;
        }
        return null;
    }
}

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: