Search in Rotated Sorted Array解答

 

the key is to locate the range which satisfy if x<y then array[x] < array[y].

then we can decide if the element is within [x,y] or outside of [x,y], narrowing down the search space by roughly half.

If there is duplicate (array[middle] == array[right],  then we can’t decide whether to throw away [x,y] entirely or jump into [x,y]. A solution is to only remove array[right] (right -=1)

Reference:

http://www.cnblogs.com/zuoyuan/p/3777422.html

http://fisherlei.blogspot.com/2013/01/leetcode-search-in-rotated-sorted-array.html

Related:

Search  for a range

http://blog.allenzhao.com/leetcode/2014/09/15/LeetCode-Search-for-a-range/

http://bangbingsyb.blogspot.com/2014/11/leecode-find-minimum-in-rotated-sorted.html

http://yucoding.blogspot.com/2014/10/leetcode-question-find-minimum-in.html

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s