《天生不对》太搞笑了，笑得人眼泪都出来了 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Movie - 无限影话

《天生不对》太搞笑了，笑得人眼泪都出来了

《天生不对》太搞笑了，笑得人眼泪都出来了# Movie - 无限影话

a*d2018-04-05 07:04

1 楼

Given a sorted list of N integers that has been rotated an unknown number of
positions, e.g., 15 36 1 7 12 13 14
design an algorithm to determine if a given integer is in the list

S*52018-04-05 07:04

2 楼

两个人天生不对，怎么在一起？
今天看了下电视剧《烈火如歌》，里面有周渝民，感觉好久没有看到他了，最近看他还
是在一部电影里面，和薛凯琪搭档出演的，电影挺好看，所以今天我心血来潮，想推荐
一下这部电影。
这部电影的男女主人设很奇葩，别人都是天生一对，他俩却是天生不对，最后居然还能
在一起，真的是真爱啊。今天我就给大家安利这部爱情轻喜电影――《天生不对》。
影片开场，男女主的相遇很不愉快，互相都很讨厌对方。男主是一个风水大师，女主是
一个普通的公司小妹，说他俩天生不对，是因为他们天生八字相克，如果在一起各自的
运势会变得非常差。女主的八字特殊，是一个衰神，天生自带煞气，处处碰壁，霉运连
连。男主在男二的设计下，误以为女主和他八字相合，所以把女主调任在他的身边当助
手，想让女主帮他挡煞气，帮他转运。后来这对欢喜冤家在相处中逐渐爱上了对方，即
使后来男主知道，和女主相处会运气越变越衰，但他俩还是不顾一切的在一起了。后来
女主知道，男主当初留她在身边，只是帮他挡煞，所以误会了男主，所幸后来误会解除
，两人和好如初。
这部电影的男二是郑中基，非常搞笑，男女主的日常也很甜蜜，想大笑放松的朋友就可
以去看这部电影哦。

h*92018-04-05 07:04

3 楼

还是log(N)亚，这和你前面问的问题有本质区别么？

a*d2018-04-05 07:04

4 楼

本质上当然是找到partition point，再分段binary search.
如何找细节上是不同的。

【在 h***9 的大作中提到】

: 还是log(N)亚，这和你前面问的问题有本质区别么？

I*s2018-04-05 07:04

5 楼

The key is:
If the first element is less than the midpoint, the first half of the array
is correctly sorted. If the midpoint is less than the last element, the
second half of the array is correctly sorted.

s*e2018-04-05 07:04

6 楼

本质上还是不一样的，这个理论上是可以不用找break point的。多一些复杂的条件判
断即可。下面的code应该work,但没优化过。
int BS_Rotate( const std::vector & A , int value)
{
int l = 0;
int u = A.size()-1;

while( l <= u)
{
int m = (l+u)/2;
if( A[m] == value) return m;

if( A[m] < value)
{
if(A[m] <= A[u] )
{
if(A[u] < value)
{
u = m - 1;
}
else
{
l = m + 1;

【在 a*d 的大作中提到】

: 本质上当然是找到partition point，再分段binary search.
: 如何找细节上是不同的。