2 Add Two Numbers

题目描述：

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1]

Example 1:

Input: [5, 7, 7, 8, 8, 10]
Output: [3,4]

题目翻译

给定一个非递减数组，找到目标元素的出现的首末位置。

示例1：

输入： [5, 7, 7, 8, 8, 10]
输出： [3,4]

注意：

1. 数组为非递减数组，找到目标元素后，与其值相等的元素肯定在其周围

解题方案

标签： Binary Search

思路：

• 使用二分查找找到目标的位置，然后分别向左右查找有没有与其值相等的元素，

代码：

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        index = self.binary_search(0, len(nums) - 1, nums, target)    # 元素首次出现位置
        if index == -1:
            return [-1, -1]

        start, end = index, index    # 开始位置与结束位置
        while end <= len(nums) - 1:
            if nums[end] == target:     # 向右查找
                end += 1
            else:
                break
        while start >= 0:
            if nums[start] == target:    # 向左查找
                start -= 1
            else:
                break

        return [start + 1, end - 1]

    def binary_search(self, low, high, nums, target):    # 二分查找目标元素
        while low <= high:
            mid = (low + high) >> 1        # 二进制向右位移1位，相当于除以2
            if target < nums[mid]:        # 小于中间值，在数组左半部分
                high = mid - 1
            elif target > nums[mid]:    #大于中间值，在数组右半部分
                low = mid + 1
            else:    # 找到目标元素
                return mid
        return -1

参考资料

• LeetCode 56ms Solution