首页 > 代码库 > leetcode 【 Search for a Range 】python 实现
leetcode 【 Search for a Range 】python 实现
题目：
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].
代码：oj测试通过 Runtime: 91 ms
1 class Solution: 2 # @param A, a list of integers 3 # @param target, an integer to be searched 4 # @return a list of length 2, [index1, index2] 5 def searchAllTarget(self, A, index, target): 6 # left index 7 left_index = index 8 curr_index = index 9 while curr_index>=0 and A[curr_index]==target:10 left_index = curr_index11 curr_index = curr_index-112 # right index13 right_index = index14 curr_index = index15 while curr_index<len(A) and A[curr_index]==target:16 right_index = curr_index17 curr_index = curr_index+118 return [left_index,right_index]19 20 def searchRange(self, A, target):21 # none case22 if A is None:23 return None24 # short length cases25 if len(A)==1 :26 return[[-1,-1],[0,0]][A[0]==target]27 # binary search28 start = 029 end = len(A)-130 while start<=end :31 if start==end:32 if A[start]==target :33 return self.searchAllTarget(A, start, target)34 else :35 return [-1,-1]36 if start+1==end :37 if A[start]==target :38 return self.searchAllTarget(A, start, target)39 elif A[end]==target :40 return self.searchAllTarget(A, end, target)41 else :42 return [-1,-1]43 mid = (start+end)/244 if A[mid]==target :45 return self.searchAllTarget(A, mid, target)46 elif A[mid]>target :47 end = mid-148 else :49 start = mid+1
思路：
这道题还是基于binary search，但是要求找到的是某个值的range。
分两步完成：
step1. 常规二分查找到target的某个index；如果没有找到则返回[-1,-1]
step2. 假设A中可能有多个位置为target，则从step1找到的index开始向左右search，直到把index左右两侧的target都找出来。
齐活儿
leetcode 【 Search for a Range 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。