Bloomberg电面

StellaJiang 发表于 2016-4-29 02:22
如果是[3,5,7,8,6,4,2]这种形式的，用binary search, 不好判定不要哪边的数吧。比如找4，第一次mid的位置 ...

这样的话就第一轮两边都不去掉（这里两边分别找的是nums[0+3],nums[6-3]，第二轮用nums[0+3/2],nums[6-3/2]来比较。我是这么想的，你可以试试。。。

我感觉是先binary search 找到定点，然后对两边分别进行binary search, 复杂度同样是 logn

补充内容 (2016-5-6 03:43):
顶点

这贴的亮点是大家在猜对方是不是印度人

先用BS找数组中最大的数（mid>mid-1 && mid<mid+1)
然后将数组分成递增和递减的两部分，分别在用BS找，总体的时间复杂度就是O(logN)

同理Leetcode 162