46.leetcode34_search_for_a

46.leetcode34_search_for_a_range

1.题目描述

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].

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

2.解题思路

双指针分别从首尾向中间移动

Python代码(47ms)

 1 class Solution(object):
 2     def searchRange(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         index1=0
 9         index2=0
10         l=len(nums)-1
11         i=0
12         while i<l+1:
13             if nums[i]<target:
14                 i+=1
15             else:
16                 index1=i
17                 break
18         while l>=0:
19             if nums[l]>target:
20                 l-=1
21             else:
22                 index2=l
23                 break
24         if target not in nums:
25             return [-1,-1]
26         return [index1,index2]