NC105 二分查找-II

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

数据范围：0<=n<=100000

进阶：时间复杂度O(logn)，空间复杂度O(n)

思路：二分法，先找到target，如果nums[middle]==target，且nums[middle-1]<target，说明middle就是要找的下标。while循环结束后，还没有return过的，可能target在数组两边，nums[0]或nums[len(num)-1]的位置。在最开始的时候判断0的情况，在while循环结束的时候判断len(num)-1的情况

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 如果目标值存在返回下标，否则返回 -1
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if len(nums) == 0:
            return -1
        if nums[0] == target:
            return 0
        left = 0
        right = len(nums) - 1
        while left < right:
            middle = (left + right) // 2
            if nums[middle] >= target:
                right = middle - 1
                if nums[right] < target:
                    if nums[middle] == target:
                        return middle
                    return -1
            else:
                left = middle + 1
        if nums[right] == target:
            return right
        return -1