首页 > 代码库 > [leetcode]Search for a Range @ Python

[leetcode]Search for a Range @ Python

2024-07-07 13:20:31   226人阅读

原题地址：https://oj.leetcode.com/problems/search-for-a-range/

题意：

Given a sorted array of integers, 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].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

解题思路：又是二分查找的变形。因为题目要求的时间复杂度是O(log n)。在二分查找到元素时，需要向前和向后遍历来找到target元素的起点和终点。

代码：

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRange(self, A, target):
        left = 0; right = len(A) - 1
        while left <= right:
            mid = (left + right) / 2
            if A[mid] > target:
                right = mid - 1
            elif A[mid] < target:
                left = mid + 1
            else:
                list = [0, 0]
                if A[left] == target: list[0] = left
                if A[right] == target: list[1] = right
                for i in range(mid, right+1):
                    if A[i] != target: list[1] = i - 1; break
                for i in range(mid, left-1, -1):
                    if A[i] != target: list[0] = i + 1; break
                return list
        return [-1, -1]

 

 


联系
我们