g*******u
发帖数: 107 | 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)? | p*****2
发帖数: 21240 | | c******a
发帖数: 789 | 3 re楼上。
要找的是左target和右target，左target的左边不是target，右target的右边不是
target。用binary search找她们就得了。 |
|
