题目
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一：双指针
思路
主要是在头尾各设置一个指针，然后进行求和，如果大于，则尾指针减一；如果小于，则头指针加一；否则，输出索引值
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
right = length - 1
left = 0
while left < right:
if numbers[left] + numbers[right] == target:
return [left+1, right+1]
elif numbers[left] + numbers[right] > target:
right -= 1
else:
left += 1
解法二：二分查找
思路
拖了两天才搞明白这个问题，其实到头来只是自己没搞懂python函数调用和递归实现的方法。
首先你要明白这题查找只是第一步，首先利用二分查找找到target - numbers[left],然后再把Index传过来，赋值给right，这样各加一就可以得到答案了。第一种方法是网友给的解法，直接用while 循环找到值，然后返回索引。而第二种方法我用到了递归实现二分查找，速度比循环慢一些。下面是代码
### 方法一（循环实现二分查找）：
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
for left in range(length - 1):
right = self.binary_chop(numbers, left + 1, length - 1, target - numbers[left])
if right != -1:
return [left + 1, right + 1]
def binary_chop(self, numbers, left, right, target):
# 在子区间 [left, right] 找 target
while left < right:
mid = (left + right) //2
if numbers[mid] < target:
left = mid + 1
else:
right = mid
return left if numbers[left] == target else -1
###方法二（递归实现二分查找）：
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
for left in range(length - 1): #对列表进行遍历
right = self.binary_chop(numbers, left + 1, length - 1, target - numbers[left]) #调用函数找值，返回Index赋值给right
if right != -1: # 返回值不是-1时，找到位置
return [left + 1, right + 1]
def binary_chop(self, numbers, left, right, target):
mid = (left + right) // 2
if left < right:
if numbers[mid] > target:
return self.binary_chop(numbers, left, mid - 1, target)
elif numbers[mid] < target:
return self.binary_chop(numbers, mid + 1, right, target)
else:
return mid
return left if numbers[left] == target else -1