x*********s
发帖数: 2604 | 1 Given a sorted array with duplicates and a number, find the range in the
form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
Upon further probe:
1. Do better than linear scan, which is O(n). 2. You can just work out how
to find the start index, and I will assume that you know how to find the end.
有没有办法用binary search来找start和end？ | c****o
发帖数: 41 | 2 感觉把binary search的停止条件换一下就可以， 找start时为x[i-1]
x[i]==value，找end时为x[i]==value && x[i+1]>value。
3 3
how
end.
【在 x*********s 的大作中提到】
: Given a sorted array with duplicates and a number, find the range in the
: form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
: 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
: Upon further probe:
: 1. Do better than linear scan, which is O(n). 2. You can just work out how
: to find the start index, and I will assume that you know how to find the end.
: 有没有办法用binary search来找start和end？
| j*****u
发帖数: 1133 | 3 先binary找到这个数O(logN)，然后向左找start，向右找end是同样的办法
可以liner也可以继续binary
3
end.
【在 x*********s 的大作中提到】
: Given a sorted array with duplicates and a number, find the range in the
: form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
: 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
: Upon further probe:
: 1. Do better than linear scan, which is O(n). 2. You can just work out how
: to find the start index, and I will assume that you know how to find the end.
: 有没有办法用binary search来找start和end？
| l*****a
发帖数: 14598 | 4 当然是继续二分
【在 j*****u 的大作中提到】
: 先binary找到这个数O(logN)，然后向左找start，向右找end是同样的办法
: 可以liner也可以继续binary
:
: 3
: end.
| j*****u
发帖数: 1133 | 5 取决于logN和重复元素个数哪个大，重复数小的时候liner更好
【在 l*****a 的大作中提到】
: 当然是继续二分
| l*****a
发帖数: 14598 | 6 how to judge that in runtime?
【在 j*****u 的大作中提到】
: 取决于logN和重复元素个数哪个大，重复数小的时候liner更好
| j*****u
发帖数: 1133 | 7 要compile time前面试官告诉，runtime就晚了 ：）
【在 l*****a 的大作中提到】
: how to judge that in runtime?
| l*****a
发帖数: 14598 | 8 if he doesn't tell u
which one will u write,just write one
【在 j*****u 的大作中提到】
: 要compile time前面试官告诉，runtime就晚了 ：）
| n*****y
发帖数: 361 | 9 性格测试？
you have to make the assumption.
ls说的很清楚了。
【在 l*****a 的大作中提到】
: if he doesn't tell u
: which one will u write,just write one
| f****g
发帖数: 313 | 10 I like this one:S
【在 c****o 的大作中提到】
: 感觉把binary search的停止条件换一下就可以， 找start时为x[i-1]: x[i]==value，找end时为x[i]==value && x[i+1]>value。
:
: 3 3
: how
: end.
| | | n*s
发帖数: 752 | 11 def sSearch(a, v):
tot_len = len(a)
l = 0
r = tot_len-1
while l < r :
m = (l+r) //2
if a[m] > v:
r = m -1
elif a[m] < v:
l = m + 1
else:
r = m # start pointer is saved here
if a[l] is v:
return r
else:
return -1
a = [1,1, 2, 3,3,3,5, 6]
print a
print sSearch(a,3)
【在 l*****a 的大作中提到】
: if he doesn't tell u
: which one will u write,just write one
| h**6
发帖数: 4160 | 12 有现成函数的，lower_bound和upper_bound | j********x
发帖数: 2330 | 13 看看stl algorithm 里面的lower_bound equal_range | f*********8
发帖数: 34 | 14 这是用python写的吗
是不是没有考虑到a[m]第一次正好等于v的情况呢，比如a[9]={0,1,2,3,3,3,4,7,10},v
=3
那么按照你的程序m=(0+8)/2=4,a[m]=3=v,那么一次就决定了r=4,但是实际上endindex=
5，因为后面还有个3，同理对求l来说也存在一样的问题。
我觉得在跳出while循环得到r后还应该再检查一下a[r+1]!=v（如果用a[r+1]>v这个判
断条件的话当v=10也就是数组最后一个数的时候会出现错判），如果a[r]==v&&a[r+1]=
=v,那么还要继续增加r直到找到a[r+1]!=v的那个r
【在 n*s 的大作中提到】
: def sSearch(a, v):
: tot_len = len(a)
: l = 0
: r = tot_len-1
: while l < r :
: m = (l+r) //2
: if a[m] > v:
: r = m -1
: elif a[m] < v:
: l = m + 1
| P********l
发帖数: 452 | | P********l
发帖数: 452 | 16 http://www.sureinterview.com/shwqst/545001
code:
public void findRange(double[] data, double rangeStart, double rangeEnd,
Mutable pStart, Mutable pEnd) {
pStart.setValue(-1);
pEnd.setValue(-1);
if (data == null || data.length == 0)
return;
int posStart = 0, posEnd = data.length - 1;
// find where the data roughly is.
int inRange = 0;
while (posStart <= posEnd) {
inRange = (posStart + posEnd) / 2;
if (data[inRange] < rangeStart) {
posStart = inRange + 1;
} else if (data[inRange] > rangeEnd) {
posEnd = inRange - 1;
} else {
// found: rangeStart <= data[inRange] <= rangeEnd;
break;
}
}
// not found
if (posStart > posEnd)
return;
// Now, data[inRange] is in the range of data.
// We need to find the index that points to rangeStart.
int pEnd2 = inRange;
while (posStart <= pEnd2) {
int n = (posStart + pEnd2) / 2;
if (data[n] < rangeStart) {
posStart = n + 1;
} else {
pEnd2 = n - 1;
}
// note: there is no break when rangeStart was found.
}
// and find the end position in [inRange,posEnd]
int pStart2 = inRange;
while (pStart2 <= posEnd) {
int n = (pStart2 + posEnd) / 2;
if (data[n] > rangeEnd) {
posEnd = n - 1;
} else {
pStart2 = n + 1;
}
// note: there is no break;
}
if (posStart <= posEnd) {
pStart.setValue(posStart);
pEnd.setValue(posEnd);
} | n*s
发帖数: 752 | 17 the return value here is the startIndex,
for endIndex, one can traverse from startIndex
,v
endindex=
]=
【在 f*********8 的大作中提到】
: 这是用python写的吗
: 是不是没有考虑到a[m]第一次正好等于v的情况呢，比如a[9]={0,1,2,3,3,3,4,7,10},v
: =3
: 那么按照你的程序m=(0+8)/2=4,a[m]=3=v,那么一次就决定了r=4,但是实际上endindex=
: 5，因为后面还有个3，同理对求l来说也存在一样的问题。
: 我觉得在跳出while循环得到r后还应该再检查一下a[r+1]!=v（如果用a[r+1]>v这个判
: 断条件的话当v=10也就是数组最后一个数的时候会出现错判），如果a[r]==v&&a[r+1]=
: =v,那么还要继续增加r直到找到a[r+1]!=v的那个r
| g*****x
发帖数: 799 | 18 void rangeBinarySearch(const vector &vec, const int val, int &range_beg
, int &range_end)
{
range_beg = -1;
range_end = -1;
int beg = 0;
int end = vec.size();
int mid;
while(beg < end)
{
mid = (end - beg) / 2 + beg;
if(vec[mid] == val && (mid == 0 || vec[mid - 1] < val))
{
range_beg = mid;
break;
}
if(vec[mid] >= val)
end = mid;
else
beg = mid + 1;
}
if(range_beg == -1)
return;
beg = mid;
end = vec.size();
while(beg < end)
{
mid = (end - beg) / 2 + beg;
if(vec[mid] == val && (mid == vec.size() - 1 || vec[mid + 1] > val))
{
range_end = mid;
break;
}
if(vec[mid] > val)
end = mid;
else
beg = mid + 1;
}
} | c******n
发帖数: 4965 | 19
the
3 3 3
1).
out how
the end.
【在 x*********s 的大作中提到】
: Given a sorted array with duplicates and a number, find the range in the
: form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
: 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
: Upon further probe:
: 1. Do better than linear scan, which is O(n). 2. You can just work out how
: to find the start index, and I will assume that you know how to find the end.
: 有没有办法用binary search来找start和end？
| c******n
发帖数: 4965 | 20 这是很好的一个题，
programming pearl 里面有， 就是binary search 升级版。
考的不是你怎么能把code 写出来，考的是怎么能prove correctness.
书里说10% programmer 能写对binary search,
这个估计能有3% 写对。
在chapter 4 的习题里面
the
2 3 3 3
1).
out how
the end.
【在 x*********s 的大作中提到】
: Given a sorted array with duplicates and a number, find the range in the
: form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
: 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
: Upon further probe:
: 1. Do better than linear scan, which is O(n). 2. You can just work out how
: to find the start index, and I will assume that you know how to find the end.
: 有没有办法用binary search来找start和end？
|
|
