问一个基本的查找问题# Programming - 葵花宝典
h*n
1 楼
我妈妈来自北方农村，勤劳，善良。有丰富的育儿经验，照顾小孩特别有耐心，而且特
别用心。她希望在家帮助照看小孩。有意者，请站内联系。
别用心。她希望在家帮助照看小孩。有意者，请站内联系。
d*u
2 楼
可以ＤＩＹ吗
l*y
3 楼
现在几乎每年大陆的电影都会有关于孙悟空的电影，现在孙悟空很受到欢迎，除了小的
时候听西游记看西游记之外。
按照荣格的集体无意识来说，孙悟空就是每个年轻人一样，在开始之前，都像孙悟空那
样一切会由着自己的性子作，但是长大了受到时间和现实社会的双层摩擦，就像那个紧
箍咒一样，开始变的老实了，没有了之前的不羁，本以为人定胜天，现在也知道了天意
不可违，百般权衡隐忍内敛，做对自己有利的事情。
年轻的时候像齐天大圣那样叛逆，去反抗，但是到了中年就像孙悟空一样，有不甘有愤
怒，有不平之意，却难以像年轻时候的猴子那样敢作敢为，为了生活，那生活就像紧箍
咒一样虽不在头上却像一道无形的枷锁，让我们束手束脚。
悟空的一生也就是每个男人的一生。
时候听西游记看西游记之外。
按照荣格的集体无意识来说，孙悟空就是每个年轻人一样，在开始之前，都像孙悟空那
样一切会由着自己的性子作，但是长大了受到时间和现实社会的双层摩擦，就像那个紧
箍咒一样，开始变的老实了，没有了之前的不羁，本以为人定胜天，现在也知道了天意
不可违，百般权衡隐忍内敛，做对自己有利的事情。
年轻的时候像齐天大圣那样叛逆，去反抗，但是到了中年就像孙悟空一样，有不甘有愤
怒，有不平之意，却难以像年轻时候的猴子那样敢作敢为，为了生活，那生活就像紧箍
咒一样虽不在头上却像一道无形的枷锁，让我们束手束脚。
悟空的一生也就是每个男人的一生。
L*o
4 楼
西行记
Lihebo
我正返回，
从梦境里，从天堂里，
还是在一个下午，
沿着十号公路一直向西。
午后的阳光白花花一片，
照得一切都那么耀眼，
看不到一丝黑暗。
其实，黑暗本不存在，
我们自己创造了它，
正如当地球以它盲目的自转
背离阳光的照耀，
黑夜就会来到。
生命的旋转也同样盲目，
尽管它们是以时间为轴。
沼泽里的秃柏枝叶疏落，
那是在水里站得太久的结果，
那些人造的高速路如堤坝
挡住了水的去处。
查尔斯湖里的金币
不停地闪烁着眼睛，
湖边的赌场张开了钱袋，
将每一个进去的人收起。
再见，路易斯安那，
还有水田里的小龙虾，
如果有一天你来到我的餐桌上，
我会装作并不认识你。
而此刻，在你最冰冷的梦里，
是否感觉到，太阳正把水烤得
越来越热，以至沸腾？
再见，黄色的烟，
你将继续轻抹白云的胸膛，
而我用纸巾抹掉嘴边的碳氢氧。
待耕的地里有犁铧在去年
留下的痕迹，野草燃烧着肉身，
以便化作春泥，于下一场春雨。
有一天当我老去，
这也是我可预见的结局。
当夕阳西斜，
路边的树林变幻着头冠的颜色，
我猛踩油门，加速前进，
迎着夕阳驰去，
以高于地球自转的表面速度，
因为我要追上夕阳，
因为我要熔入夕阳，
因为我要超越夕阳，
这样我就能再回到朝阳里。
（2013年2月1日构思于从路易斯安那返回德克萨斯的途中，写就于2月4日。）
Lihebo
我正返回，
从梦境里，从天堂里，
还是在一个下午，
沿着十号公路一直向西。
午后的阳光白花花一片，
照得一切都那么耀眼，
看不到一丝黑暗。
其实，黑暗本不存在，
我们自己创造了它，
正如当地球以它盲目的自转
背离阳光的照耀，
黑夜就会来到。
生命的旋转也同样盲目，
尽管它们是以时间为轴。
沼泽里的秃柏枝叶疏落，
那是在水里站得太久的结果，
那些人造的高速路如堤坝
挡住了水的去处。
查尔斯湖里的金币
不停地闪烁着眼睛，
湖边的赌场张开了钱袋，
将每一个进去的人收起。
再见，路易斯安那，
还有水田里的小龙虾，
如果有一天你来到我的餐桌上，
我会装作并不认识你。
而此刻，在你最冰冷的梦里，
是否感觉到，太阳正把水烤得
越来越热，以至沸腾？
再见，黄色的烟，
你将继续轻抹白云的胸膛，
而我用纸巾抹掉嘴边的碳氢氧。
待耕的地里有犁铧在去年
留下的痕迹，野草燃烧着肉身，
以便化作春泥，于下一场春雨。
有一天当我老去，
这也是我可预见的结局。
当夕阳西斜，
路边的树林变幻着头冠的颜色，
我猛踩油门，加速前进，
迎着夕阳驰去，
以高于地球自转的表面速度，
因为我要追上夕阳，
因为我要熔入夕阳，
因为我要超越夕阳，
这样我就能再回到朝阳里。
（2013年2月1日构思于从路易斯安那返回德克萨斯的途中，写就于2月4日。）
a*y
5 楼
现在还可以让Apple Expert在约定时间call你
E*F
6 楼
在一个sorted array里查找“第一次”出现的0
如果用基于比较的方法，复杂度是多少？
我看网上有些人说是O(logn)，可我觉得不对
O(logn)只能找到想查找的元素，
但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
要么得在前面的区间里再用binary search,
如果碰到极端的情况要用很多次直到只有一个元素
所以怎么也不可能是O(logn)啊
如果用基于比较的方法，复杂度是多少？
我看网上有些人说是O(logn)，可我觉得不对
O(logn)只能找到想查找的元素，
但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
要么得在前面的区间里再用binary search,
如果碰到极端的情况要用很多次直到只有一个元素
所以怎么也不可能是O(logn)啊
s*a
7 楼
一万米怎么跑？我能跑下来吗？
【在 d****u 的大作中提到】
: 可以ＤＩＹ吗
【在 d****u 的大作中提到】
: 可以ＤＩＹ吗
s*t
8 楼
好长的东东
【在 L****o 的大作中提到】
: 西行记
: Lihebo
: 我正返回，
: 从梦境里，从天堂里，
: 还是在一个下午，
: 沿着十号公路一直向西。
: 午后的阳光白花花一片，
: 照得一切都那么耀眼，
: 看不到一丝黑暗。
: 其实，黑暗本不存在，
【在 L****o 的大作中提到】
: 西行记
: Lihebo
: 我正返回，
: 从梦境里，从天堂里，
: 还是在一个下午，
: 沿着十号公路一直向西。
: 午后的阳光白花花一片，
: 照得一切都那么耀眼，
: 看不到一丝黑暗。
: 其实，黑暗本不存在，
a*y
9 楼
昨天下午五点半以后和苹果通电话
不到24小时replacement耳机就寄到了。
中国要达到这个效率，看来只有靠私营快递了。
【在 a***y 的大作中提到】
: 现在还可以让Apple Expert在约定时间call你
不到24小时replacement耳机就寄到了。
中国要达到这个效率，看来只有靠私营快递了。
【在 a***y 的大作中提到】
: 现在还可以让Apple Expert在约定时间call你
G*7
10 楼
why not. you can do o(log(n)) with a variant of binary search that
alternatives between looking for an element smaller than your query and
looking an element equal to your query. in doing so you will bracket the
first occurrence of your query.
check out, for instance, std::equal_range in. equal_range finds
the first and last occurrence of the query in 2*o(log(n)).
【在 E*******F 的大作中提到】
: 在一个sorted array里查找“第一次”出现的0
: 如果用基于比较的方法，复杂度是多少？
: 我看网上有些人说是O(logn)，可我觉得不对
: O(logn)只能找到想查找的元素，
: 但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
: 要么得在前面的区间里再用binary search,
: 如果碰到极端的情况要用很多次直到只有一个元素
: 所以怎么也不可能是O(logn)啊
alternatives between looking for an element smaller than your query and
looking an element equal to your query. in doing so you will bracket the
first occurrence of your query.
check out, for instance, std::equal_range in
the first and last occurrence of the query in 2*o(log(n)).
【在 E*******F 的大作中提到】
: 在一个sorted array里查找“第一次”出现的0
: 如果用基于比较的方法，复杂度是多少？
: 我看网上有些人说是O(logn)，可我觉得不对
: O(logn)只能找到想查找的元素，
: 但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
: 要么得在前面的区间里再用binary search,
: 如果碰到极端的情况要用很多次直到只有一个元素
: 所以怎么也不可能是O(logn)啊
M*o
11 楼
以前公司是怎么报的税呢？
其实我觉得如果自己有些基础会计知识，懂些deduction的话，自己买TurboTax
Business version，一步一步跟着instructions走，应该可以搞定。
其实我觉得如果自己有些基础会计知识，懂些deduction的话，自己买TurboTax
Business version，一步一步跟着instructions走，应该可以搞定。
L*o
12 楼
嗯，比某婆娘的裹脚布还长点，呵呵。
【在 s**t 的大作中提到】
: 好长的东东
【在 s**t 的大作中提到】
: 好长的东东
P*a
13 楼
你在东岸，五点半以后苹果太平洋时间还没下班呢
【在 a***y 的大作中提到】
: 昨天下午五点半以后和苹果通电话
: 不到24小时replacement耳机就寄到了。
: 中国要达到这个效率，看来只有靠私营快递了。
【在 a***y 的大作中提到】
: 昨天下午五点半以后和苹果通电话
: 不到24小时replacement耳机就寄到了。
: 中国要达到这个效率，看来只有靠私营快递了。
E*F
14 楼
那你怎么保证较小的元素是最后一个呢。
再说也不知道都有哪些
要找出那个界限constant time是不行的啊
finds
【在 G*****7 的大作中提到】
: why not. you can do o(log(n)) with a variant of binary search that
: alternatives between looking for an element smaller than your query and
: looking an element equal to your query. in doing so you will bracket the
: first occurrence of your query.
: check out, for instance, std::equal_range in. equal_range finds
: the first and last occurrence of the query in 2*o(log(n)).
再说也不知道都有哪些
要找出那个界限constant time是不行的啊
finds
【在 G*****7 的大作中提到】
: why not. you can do o(log(n)) with a variant of binary search that
: alternatives between looking for an element smaller than your query and
: looking an element equal to your query. in doing so you will bracket the
: first occurrence of your query.
: check out, for instance, std::equal_range in
: the first and last occurrence of the query in 2*o(log(n)).
n*y
15 楼
I did this with TurboTax in half hour.
【在 d****u 的大作中提到】
: 可以ＤＩＹ吗
【在 d****u 的大作中提到】
: 可以ＤＩＹ吗
s*t
16 楼
太谦虚了，你。
【在 L****o 的大作中提到】
: 嗯，比某婆娘的裹脚布还长点，呵呵。
【在 L****o 的大作中提到】
: 嗯，比某婆娘的裹脚布还长点，呵呵。
a*y
17 楼
我知道啊。
【在 P***a 的大作中提到】
: 你在东岸，五点半以后苹果太平洋时间还没下班呢
【在 P***a 的大作中提到】
: 你在东岸，五点半以后苹果太平洋时间还没下班呢
t*t
18 楼
人都跟你说了看一下std::equal_range.
【在 E*******F 的大作中提到】
: 那你怎么保证较小的元素是最后一个呢。
: 再说也不知道都有哪些
: 要找出那个界限constant time是不行的啊
:
: finds
【在 E*******F 的大作中提到】
: 那你怎么保证较小的元素是最后一个呢。
: 再说也不知道都有哪些
: 要找出那个界限constant time是不行的啊
:
: finds
S*e
19 楼
美国很多地方开车，确实非常壮观。这两首非常棒。
【在 L****o 的大作中提到】
: 嗯，比某婆娘的裹脚布还长点，呵呵。
【在 L****o 的大作中提到】
: 嗯，比某婆娘的裹脚布还长点，呵呵。
r*t
20 楼
你耳机咋了？
是inear那个的吗？
【在 a***y 的大作中提到】
: 昨天下午五点半以后和苹果通电话
: 不到24小时replacement耳机就寄到了。
: 中国要达到这个效率，看来只有靠私营快递了。
是inear那个的吗？
【在 a***y 的大作中提到】
: 昨天下午五点半以后和苹果通电话
: 不到24小时replacement耳机就寄到了。
: 中国要达到这个效率，看来只有靠私营快递了。
l*s
21 楼
you locate the bounds by finding the nearest smaller/larger instead.
【在 E*******F 的大作中提到】
: 那你怎么保证较小的元素是最后一个呢。
: 再说也不知道都有哪些
: 要找出那个界限constant time是不行的啊
:
: finds
【在 E*******F 的大作中提到】
: 那你怎么保证较小的元素是最后一个呢。
: 再说也不知道都有哪些
: 要找出那个界限constant time是不行的啊
:
: finds
L*o
22 楼
嗯，给我留下最深印象的是熊牙高速，Beartooth Highway。贴两张快开到山顶时拍的
照片。
【在 S*********e 的大作中提到】
: 美国很多地方开车，确实非常壮观。这两首非常棒。
照片。
【在 S*********e 的大作中提到】
: 美国很多地方开车，确实非常壮观。这两首非常棒。
a*y
23 楼
是的。第一批的耳机插口接头背后的塑料太软容易松动，看到网上有人的完全脱了。
送了的话mic和remote就不work了。
【在 r*****t 的大作中提到】
: 你耳机咋了？
: 是inear那个的吗？
送了的话mic和remote就不work了。
【在 r*****t 的大作中提到】
: 你耳机咋了？
: 是inear那个的吗？
E*F
24 楼
嗯，如果元素都是整数，这个办法是可以的
如果是任意实数，似乎无法确定nearest smaller one
不过实际问题中也用不到了
【在 l*********s 的大作中提到】
: you locate the bounds by finding the nearest smaller/larger instead.
如果是任意实数，似乎无法确定nearest smaller one
不过实际问题中也用不到了
【在 l*********s 的大作中提到】
: you locate the bounds by finding the nearest smaller/larger instead.
w*a
25 楼
漂亮，希望有机会感受一下。
【在 L****o 的大作中提到】
: 嗯，给我留下最深印象的是熊牙高速，Beartooth Highway。贴两张快开到山顶时拍的
: 照片。
【在 L****o 的大作中提到】
: 嗯，给我留下最深印象的是熊牙高速，Beartooth Highway。贴两张快开到山顶时拍的
: 照片。
f*8
26 楼
不少公司都喜欢用这种overnight来寄replacement，邮费比东西还贵挺不划算的
【在 a***y 的大作中提到】
: 昨天下午五点半以后和苹果通电话
: 不到24小时replacement耳机就寄到了。
: 中国要达到这个效率，看来只有靠私营快递了。
【在 a***y 的大作中提到】
: 昨天下午五点半以后和苹果通电话
: 不到24小时replacement耳机就寄到了。
: 中国要达到这个效率，看来只有靠私营快递了。
l*s
27 楼
glock17 and thrust already told you the answer, equal_range does exactly
this.
【在 E*******F 的大作中提到】
: 嗯，如果元素都是整数，这个办法是可以的
: 如果是任意实数，似乎无法确定nearest smaller one
: 不过实际问题中也用不到了
this.
【在 E*******F 的大作中提到】
: 嗯，如果元素都是整数，这个办法是可以的
: 如果是任意实数，似乎无法确定nearest smaller one
: 不过实际问题中也用不到了
a*y
28 楼
他们大概有合同价格吧
【在 f***8 的大作中提到】
: 不少公司都喜欢用这种overnight来寄replacement，邮费比东西还贵挺不划算的
【在 f***8 的大作中提到】
: 不少公司都喜欢用这种overnight来寄replacement，邮费比东西还贵挺不划算的
t*t
29 楼
equal_range没说只对整数, 只要能比较就行了.
【在 E*******F 的大作中提到】
: 嗯，如果元素都是整数，这个办法是可以的
: 如果是任意实数，似乎无法确定nearest smaller one
: 不过实际问题中也用不到了
【在 E*******F 的大作中提到】
: 嗯，如果元素都是整数，这个办法是可以的
: 如果是任意实数，似乎无法确定nearest smaller one
: 不过实际问题中也用不到了
c*m
30 楼
please define "第一个".
难道你找到的第一个不是人家要找的第一个么？
【在 E*******F 的大作中提到】
: 在一个sorted array里查找“第一次”出现的0
: 如果用基于比较的方法，复杂度是多少？
: 我看网上有些人说是O(logn)，可我觉得不对
: O(logn)只能找到想查找的元素，
: 但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
: 要么得在前面的区间里再用binary search,
: 如果碰到极端的情况要用很多次直到只有一个元素
: 所以怎么也不可能是O(logn)啊
E*F
31 楼
没什么特别的，就是地址最小的那个
一个极端的情况，如果输入数组元素全部都是0
如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
我看了一下网上一些人的折半查找code和讨论，全部都是错的
他们都假设只需要调用constant次的折半查找过程
其实根本不是
不过对于average case是没错
【在 c*****m 的大作中提到】
:
: please define "第一个".
: 难道你找到的第一个不是人家要找的第一个么？
一个极端的情况，如果输入数组元素全部都是0
如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
我看了一下网上一些人的折半查找code和讨论，全部都是错的
他们都假设只需要调用constant次的折半查找过程
其实根本不是
不过对于average case是没错
【在 c*****m 的大作中提到】
:
: please define "第一个".
: 难道你找到的第一个不是人家要找的第一个么？
c*m
32 楼
你理解了这些O(logn)的算法的前提是这个数列是sorted的吧？
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
t*t
33 楼
为什么全是0的情况下找不到第一个0?
找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
哪里, 也不明白为什么你不愿意看一下现成的STL code.
最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
哪里, 也不明白为什么你不愿意看一下现成的STL code.
最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
E6
34 楼
没有看懂,
如果都是0
应该还是LG(N)啊
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
如果都是0
应该还是LG(N)啊
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
b*i
35 楼
他是真逗
【在 E6 的大作中提到】
: 没有看懂,
: 如果都是0
: 应该还是LG(N)啊
【在 E6 的大作中提到】
: 没有看懂,
: 如果都是0
: 应该还是LG(N)啊
E*F
36 楼
同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
这不是common sense？
【在 t****t 的大作中提到】
: 为什么全是0的情况下找不到第一个0?
: 找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
: 就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
: 到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
: std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
: 哪里, 也不明白为什么你不愿意看一下现成的STL code.
: 最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
这不是common sense？
【在 t****t 的大作中提到】
: 为什么全是0的情况下找不到第一个0?
: 找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
: 就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
: 到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
: std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
: 哪里, 也不明白为什么你不愿意看一下现成的STL code.
: 最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
E*F
37 楼
你仔细想想
log(n)+log(n/2)+log(n/4)....+log(1)
这个级数求和会是logn吗
总共有logn项呢，不是常数个项
当然这只是worse case
还有，如果都是整数也好办，直接查找-0.5就行了
【在 E6 的大作中提到】
: 没有看懂,
: 如果都是0
: 应该还是LG(N)啊
log(n)+log(n/2)+log(n/4)....+log(1)
这个级数求和会是logn吗
总共有logn项呢，不是常数个项
当然这只是worse case
还有，如果都是整数也好办，直接查找-0.5就行了
【在 E6 的大作中提到】
: 没有看懂,
: 如果都是0
: 应该还是LG(N)啊
E*F
38 楼
全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
当然，遇到这种特殊情况，折半查找不是最优化的
但我的意思是如果用这样的方法，每次跟一个mid比，
要比logn次才能比完
虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
应该是O(logn*logn)
【在 c*****m 的大作中提到】
:
: 你理解了这些O(logn)的算法的前提是这个数列是sorted的吧？
当然，遇到这种特殊情况，折半查找不是最优化的
但我的意思是如果用这样的方法，每次跟一个mid比，
要比logn次才能比完
虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
应该是O(logn*logn)
【在 c*****m 的大作中提到】
:
: 你理解了这些O(logn)的算法的前提是这个数列是sorted的吧？
p*o
39 楼
Can you read C++? Here is the O(log n) implementation that finds the first
_Val if there is any _Val in the sorted sequence _First to _Last.
template inline
_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
{ // find first element not before _Val, using operator<
_Diff _Count = 0;
_Distance(_First, _Last, _Count);
for (; 0 < _Count; )
{ // divide and conquer, find half that contains answer
_Diff _Count2 = _Count / 2;
_FwdIt _Mid = _First;
_STD advance(_Mid, _Count2);
if (*_Mid < _Val)
{ // try top half
_First = ++_Mid;
_Count -= _Count2 + 1;
}
else
_Count = _Count2;
}
return (_First);
}
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
_Val if there is any _Val in the sorted sequence _First to _Last.
template
_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
{ // find first element not before _Val, using operator<
_Diff _Count = 0;
_Distance(_First, _Last, _Count);
for (; 0 < _Count; )
{ // divide and conquer, find half that contains answer
_Diff _Count2 = _Count / 2;
_FwdIt _Mid = _First;
_STD advance(_Mid, _Count2);
if (*_Mid < _Val)
{ // try top half
_First = ++_Mid;
_Count -= _Count2 + 1;
}
else
_Count = _Count2;
}
return (_First);
}
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
p*o
40 楼
count每次至少减一半，你说要多少次？
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
E6
41 楼
白痴?
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
t*t
42 楼
一共两次折半查找, 为什么复杂度不是log n?
【在 E*******F 的大作中提到】
: 同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
: 这不是common sense？
【在 E*******F 的大作中提到】
: 同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
: 这不是common sense？
t*t
43 楼
哪来的求和啊.
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
t*t
44 楼
你除了查找一个确定的数, 不会查别的了吗? 有没有这么难沟通啊...
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
h*s
45 楼
logn+logn --> logn
没错啊
【在 E*******F 的大作中提到】
: 同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
: 这不是common sense？
没错啊
【在 E*******F 的大作中提到】
: 同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
: 这不是common sense？
E*F
46 楼
可能我误解了你的意思
你前面不是说要查找logn次吗
还是那个极端的例子，如果全是0，要找第一个0
第一次折半，找到中间那个0（假设总是跟mid比较）
第二次折半，找到1/4处那个0
是这样吗？还是我误解了你的意思
【在 t****t 的大作中提到】
: 一共两次折半查找, 为什么复杂度不是log n?
你前面不是说要查找logn次吗
还是那个极端的例子，如果全是0，要找第一个0
第一次折半，找到中间那个0（假设总是跟mid比较）
第二次折半，找到1/4处那个0
是这样吗？还是我误解了你的意思
【在 t****t 的大作中提到】
: 一共两次折半查找, 为什么复杂度不是log n?
E*F
47 楼
好了，我想清楚了
确实是O(logn)
我想的方法复杂了，就是每次折半以后，再search for key
其实直接找mid跟key比较就可以了，不用search for key
谢谢讨论
确实是O(logn)
我想的方法复杂了，就是每次折半以后，再search for key
其实直接找mid跟key比较就可以了，不用search for key
谢谢讨论
t*t
48 楼
当然啊, 这不是common sense吗?
【在 E*******F 的大作中提到】
: 可能我误解了你的意思
: 你前面不是说要查找logn次吗
: 还是那个极端的例子，如果全是0，要找第一个0
: 第一次折半，找到中间那个0（假设总是跟mid比较）
: 第二次折半，找到1/4处那个0
: 是这样吗？还是我误解了你的意思
【在 E*******F 的大作中提到】
: 可能我误解了你的意思
: 你前面不是说要查找logn次吗
: 还是那个极端的例子，如果全是0，要找第一个0
: 第一次折半，找到中间那个0（假设总是跟mid比较）
: 第二次折半，找到1/4处那个0
: 是这样吗？还是我误解了你的意思
E*F
49 楼
不错，我开始想的就是在剩下的数组里查找key
其实只要直接用mid比就可以了
所以我想的那个方法过于复杂
【在 t****t 的大作中提到】
: 你除了查找一个确定的数, 不会查别的了吗? 有没有这么难沟通啊...
其实只要直接用mid比就可以了
所以我想的那个方法过于复杂
【在 t****t 的大作中提到】
: 你除了查找一个确定的数, 不会查别的了吗? 有没有这么难沟通啊...
c*n
50 楼
对于sorted sequence，存在相等情况的时候
如果
1. 第一个0和最后一个0是等价的，那么二分查找只要一次
中间那个0，左右一看，都相等，那就是这个0了
2. 需要找到地址（序列号）最小的那个0，
二分查找最坏情况log n次，这个界比O(log n)还紧
【在 t****t 的大作中提到】
: 为什么全是0的情况下找不到第一个0?
: 找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
: 就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
: 到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
: std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
: 哪里, 也不明白为什么你不愿意看一下现成的STL code.
: 最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
如果
1. 第一个0和最后一个0是等价的，那么二分查找只要一次
中间那个0，左右一看，都相等，那就是这个0了
2. 需要找到地址（序列号）最小的那个0，
二分查找最坏情况log n次，这个界比O(log n)还紧
【在 t****t 的大作中提到】
: 为什么全是0的情况下找不到第一个0?
: 找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
: 就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
: 到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
: std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
: 哪里, 也不明白为什么你不愿意看一下现成的STL code.
: 最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
c*n
51 楼
二分查找的任何一步的起始值比0大比0小都可以啊
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
G*7
52 楼
are you serious.
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
c*e
53 楼
这个贴子是我今年看到最逗的。删了吧。
【在 E*******F 的大作中提到】
: 好了，我想清楚了
: 确实是O(logn)
: 我想的方法复杂了，就是每次折半以后，再search for key
: 其实直接找mid跟key比较就可以了，不用search for key
: 谢谢讨论
【在 E*******F 的大作中提到】
: 好了，我想清楚了
: 确实是O(logn)
: 我想的方法复杂了，就是每次折半以后，再search for key
: 其实直接找mid跟key比较就可以了，不用search for key
: 谢谢讨论
E*F
54 楼
也没什么逗的，人有时候陷入思维定式而已
【在 c*********e 的大作中提到】
: 这个贴子是我今年看到最逗的。删了吧。
【在 c*********e 的大作中提到】
: 这个贴子是我今年看到最逗的。删了吧。
相关阅读
同时写两个平台的app？(链接) Category Theory for Programmers by Bartosz Milewski有人了解Kerberos ticket, OpenSSO, OpenID, OpenID Connect吗？问一个Java best practices怎么准备一些hardcore C++的interview (转载)大牛们如何看待Rust？有没有bootstrap+angularJS+NODEJS的templateMacBook Pro 用来做开发是不是不好用?王垠 怎样尊重一个程序员https://www.theeffectiveengineer.com/bookpython 还能活几年？简单算法问题现在的趋势是广好还是专好想请在google工作的大侠帮个忙， 帮我找一下HR的email 因为让老印给黑了有人用过J2Obc吗？牛人就是拽：Linus Torvalds一直讨厌这11项技术选哪个？ CS Masters at Columbia vs Rutgers做gui的eclipse rcp有人用过么以前有一篇Pinterest员工的架构文章现在还有必要学多线程吗？Programming model快变了