[Leetcode Solution] Find Minimum in Rotated Sorted Array I && II

It's pretty straightforward that this is a binary search problem.

The key part of binary search is how to decrease the searching scale. There are two types of scale down strategy based on the different scale down factor.

Let find(num,x,p,q) denote that find the target x in the range from num[p] to num[q]. Thus the first step we need to make sure is that whether target is located within this range. An important point needed to mind is that (p,q) denotes the target is located in range (p,q) inclusively and thus each step we decrease the range, the statement that the target is located in the range is always held.

Two things about binary search

1. Terminate condition
2. How to decrease range

Based on different types of above method, two types of implementation emerged.

1. Find out the mid element. Decrease the range (p,q) to (p,mid) or (mid,q). Thus the problem is that  the procedure might be endless because p could be always not equal to q. Hence the terminate condition is that (if p==mid) return the target which is the case that p==q or p==q-1
2. Find out the mid element. Decrease the range (p,q) to (p,mid-1) or (mid+1,q). This can make sure  that binary search procedure will sure terminate by p==q. However the thing needed to do for this method is that you must make sure if mid is the target because each time of decrease range you always eliminate the mid from next searching range.

Now let's consider the Problem "Find Minimum in Rotated Sorted Array"

1. Use first type of binary search
2. Use second type of binary search

Now let's consider the Problem  "Find Minimum in Rotated Sorted Array II"

Because duplicated elements exist. Thus it is hard to check whether mid element is the target. So we can use the first method to implement the binary search easilier.