Leetcode 33: Search in sorted rotated array

March 23, 2016

understand the algorithm - good analysis graph in the following blog:
http://fisherlei.blogspot.ca/2013/01/leetcode-search-in-rotated-sorted-array.html


using this analysis in the blog:
First, Julia, you have to find out which half is sorted; only one of them;
Second, use sorted half to determine if the search is in the sorted half or not;
Then, you go to sorted half/ unsorted half.

Code can be optimized, if it is in sorted half, then, go to normal binary search
otherwise, go to unsorted - modified binary search - use recursive to write a solution first.

http://bangbingsyb.blogspot.ca/2014/11/leetcode-search-in-rotated-sorted-array.html


Julia, in your practice, you discuss that the middle point is a peak element/ valley element or not; and then, both halves are sorted, which is the special case.

Lesson learned:

1. In your analysis, you have to make the test case as simple as possible, as you see in the above blog:
use 0 -7,
原数组：0 1 2 4 5 6 7
情况1：  6 7 0 1 2 4 5    起始元素0在中间元素的左边
情况2：  2 4 5 6 7 0 1    起始元素0在中间元素的右边

2. And then, you have to be careful, how many cases are then discussed. The above, two cases, using 0 as search element

3. 两种情况都有半边是完全sorted的。根据这半边，当target != A[mid]时，可以分情况判断：
Actually, you should add one more restriction, search half is sorted in ascending order. 

because the half of 6 7 0 1, 6 > 1, in the descending half, it must include going up and then going down. but, 
in the ascending half, 1 2 4 5, just pure ascending. <- you can argue that, it is a fact!