[Leetcode Solution] Search in Rotated Sorted Array

Analysis

• Pretty interesting a problem 
• Binary search is still available however modification should be added when update the edge at the recursion timing.
• There are several conditions needed to be handled separately (Let st,ed,mid denote the start, end and mid index)
• If target = A[mid], find it
• If A[st] <= A[ed], this is a ordered sequence
• if target < A[mid], ed=mid-1;
• if target > A[mid], st=mid+1;
• If A[st] > A[ed] means this is a rotated sequence
• If A[st] < A[mid], all of the first half sequence is the bigger part
• If target < A[mid], there are two sub-sequence might contain the target because the first half is the bigger one
• If target < A[st], st=mid+1
• If target > A[st], ed=mid-1
• If target > A[mid], st=mid+1;
• If A[st] > A[mid] means that although the sequence is rotated into two part, but the mid element is belong to the original smaller part
• If target < A[mid], ed=mid-1
• If target > A[mid], there are two sub-sequence might contain the target because the first half is the bigger one
• If target < A[ed], st=mid+1;
• if target > A[ed], ed=mid-1

Note

• Dealing with the binary search, decision whether to use < or <=, > or >= must be very very careful. Like in the termination condition while sentence and condition if sentence. The condition of two variables are equal mush be considered and decide whether to use =.

Code

UPDATED AT LEETCODE 2ND PASS