Amazon Intern面经

恭喜楼主！

xiaozhuxiaozhu 发表于 2016-1-9 07:29
我比较了啊， 10的左边比他大，右边比他小，但是因为不是sorted，所以左边右边都可能出现比他小的数

对呀，那就在左边找到pivot为止呀。

lpx1989 发表于 2016-1-9 07:28
我想到一个方法，第一遍logN找到最小点，然后分两边各搜一下，其实还是logN。就找到了

{1, 3, 50, 10, 9, 7, 6}
这种数组的最小点一定是最左，或者最又。

可行方法是，找到最大点，然后把array parition成2部分，然后每部分都会是单一上升，或者下降。
然后在写2个binary search一个是上升的，一个是下降的。
所以这题需要写3个binary search

xiaozhuxiaozhu 发表于 2016-1-9 07:34
{1, 3, 50, 10, 9, 7, 6}
这种数组的最小点一定是最左，或者最又。

对，但是有可能在第二个binary search就找到了，直接return了。

yhfyhf 发表于 2016-1-9 07:31
对呀，那就在左边找到pivot为止呀。

{1, 3, 50, 10, 9, 7, 6}

把这个array看成这样
1，x, 50, 10, 9, x, 6

比如我要找7， 然后7可以出现在这2个 x 的任何一个位置。

xiaozhuxiaozhu 发表于 2016-1-9 07:35
{1, 3, 50, 10, 9, 7, 6}

把这个array看成这样

哦哦 我忘了是返回true/false还是index。反正算法对了就行了，这个不重要哈哈哈哈

yhfyhf 发表于 2016-1-9 07:37
哦哦 我忘了是返回true/false还是index。反正算法对了就行了，这个不重要哈哈哈哈

不是返回index的问题。。
是一个binary search没发做啊。
{1, 3, 50, 10, 9, 7, 6}
binary search第一部找pivot, 10是pivot,但是下一部呢？怎么判断是向左走还是向又走呢？

xiaozhuxiaozhu 发表于 2016-1-9 07:40
不是返回index的问题。。
是一个binary search没发做啊。
{1, 3, 50, 10, 9, 7, 6}

你这例子，50才是pivot呀。。

yhfyhf 发表于 2016-1-9 07:41
你这例子，50才是pivot呀。。

我读书特别少，你千万别骗我。。。
0 + ( 6-0)/2 = 3
arr[3] = 10...

yhfyhf 发表于 2016-1-9 07:41
你这例子，50才是pivot呀。。

pivot是50，存在相同问题，，该左该又。。