[数据结构与算法]python二分查找

第一题题目是：

给定一个?n?个元素有序的（升序）整型数组?nums 和一个目标值?target ?，写一个函数搜索?nums?中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例?2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

在pyton中可以直接用index()来返回元素的下标，哈哈感觉有点小作弊。当然还是用算法来实现吧

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

?感觉思路看着还是很清晰的。定义左边界left和右边界right,之后循环对比中间下标与目标下标的大小，如果中间下标小于目标下标，则代表目标元素在右边，反之在左边。然后重新定义中间下标，以此类推...直到left大于right越界则表示列表中没有目标值，返回-1

第二题题目是：

在一个严格递减的数组中，找到第二个比目标值target大的数的下标。若不存在，则返回-1

这个跟上一题差不多，一开始我想的是把找出大于target的下标放在一个新的列表里，然后排序取列表第二个，之后突然发现造出了target就直接将它的索引-2再判断-2之后的索引存不存在就好了。这里跟上一题不同的是数组是递减的，所以判断之后left和right要交换一下。

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

第三题题目：
?

给定一个已按照 非递减顺序排列??的整数数组?numbers ，请你从数组中找出两个数满足相加之和等于目标数?target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

def TowSum(numbers, target):
    for a in numbers:
        k = numbers.index(a) + 1
        for b in numbers[k:]:
            if a + b == target:
                return sorted([numbers.index(a)+1, numbers.index(b)+1])
    return -1

这里我直接双层遍历整个列表，第一层是从头开始，第二层从第一层的元素的后一个开始，因为不可以使用相同的元素。还有=一个要注意的点是这个numbers下标从1开始，所以最后再把得出来的下标加1就ok。