二分查找

给定一个 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

python

解一：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return nums.index(target)
        else:
            return -1

解二：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)
        while(left < right):
            middle = (left + right)//2
            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] >target:
                right = middle
            elif :
                return middle
        return -1

解二

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)-1
        while(left <= right):
            middle = (left + right)//2
            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] >target:
                right = middle - 1
            else:
                return middle
        return -1

C

笔记

1. 二分查找需要注意对区间的定义：target所在区间可能为[a,b）,也可能为[a,b],当使用左闭右开区间时，右端点是没有意义的，因此left < right , right = middle,而在使用闭区间时，右端点有意义，因此left <= right , right = middle -1 ，这也是解二和解三的区别；
2. python中index()方法，可以查找列表中对应元素的位置，除了代码中用法外，还可以给它第二、三个参数，例如nums.index(target,2，4) ，使其从列表中第2个元素开始找target对应索引到第4个元素处停止（序号从0开始）。