怎么训练狗狗去帮我捡球啊# pets - 心有所宠
g*u
1 楼
Search for a Range － leetcode
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(n)。worst case, 如果所有的值都是要找的值，是不
是所有的数字都要被用来比较？
有没有真正的worst case O(log n)?
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(n)。worst case, 如果所有的值都是要找的值，是不
是所有的数字都要被用来比较？
有没有真正的worst case O(log n)?
