二分查找-II

问题描述

请实现有重复数字的升序数组的二分查找。给定一个 元素有序的（升序），长度为n的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1。

示例：

输入：[1，2，4，4，5]，4

输出：2

解释：从左到右，查找到第1个为元素4的下标为2，所以返回2。

分析问题

因为数组中的元素是单调递增的，所以我们可以使用二分查找来求解。由于是寻找数组中第一个等于目标值的元素，所以我们不能简单的判断nums[mid]==target，因为此时mid有可能是如下三种情况。对于后两种来说，寻找到的4显然不是数组中第一个等于目标值的元素，当遇到后两种情况来说，我们需要继续先前寻找，因此我们的判断条件是当nums[mid]>=target时，我们继续向左寻找，即right=mid。

下面我们来看一下整体的算法流程。

1. 执行mid=(left+right)/2
2. 如果nums[mid]<target，即寻找的元素在mid的右边，所以执行left=mid+1；如果nums[mid]>=target，表示寻找的元素为mid或者在mid的左边，所以执行right=mid。
3. 循环执行1、2步，直到left>=right。最后如果nums[right]==target，表明right就是数组中第一个等于目标元素的下标位置。

更多题解，请关注公众号【程序员学长】。这里有100多道高频算法题题解。

class Solution:
    def search(self , nums , target ):
        # write code here
        n=len(nums)
        #如果数组为空，肯定不存在target,直接返回-1
        if n==0:
            return -1
        left=0
        right=n-1
        #二分查找，寻找数组中第一个等于目标值的元素
        while left < right:
            mid=int((left+right)/2)
            if nums[mid]>=target:
                right=mid
            else:
                left=mid+1

        if nums[right]==target:
            return right
        else:
            return -1