Given a sorted array of n integers, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
O(log n) time.
这个题目的思路就是用两个binary search, 分别求first index 和last index.
Code 其实可以利用helper funciton来去优化code.
class Solution: def searchRange(self, A, target): # write your code here if not A: return [-1,-1] l, r , ans = 0, len(A) -1, [-1,-1] while l + 1 < r: mid = l + (r - l)//2 if A[mid] < target: l = mid elif A[mid] > target: r = mid else: r = mid if A[l] == target: ans[0] = l elif A[r] == target: ans[0] = r else: return ans # find last index l, r = 0, len(A) -1 while l + 1 < r: mid = l + (r - l)//2 if A[mid] < target: l = mid elif A[mid] > target: r = mid else: l = mid if A[r] == target: ans[1] = r elif A[l] == target: ans[1] = l else: return ans return ans
[LintCode] 61. Search for a Range_Easy tag: Binary Search
原文：https://www.cnblogs.com/Johnsonxiong/p/9552577.html