81 Search in Rotated Sorted Array II 详细解答

81 Search in Rotated Sorted Array II 详细解答

由于题目要求时间复杂度是O(log n), 很容易想到二分法。
但应该怎么构造二分？
举例： nums = [4,5,6,7,0,1,2], target = 0
step 1: l, r = 0, 6, mid = 3, 此时 nums[3] 先跟 nums[l] 比较
如果 nums[3] > nums[l]，说明从 l – > mid是个递增的序列，再寻找 target 是否在 (nums[l], nums[3]) 之间，如果是，缩小范围使得 r = mid -1，如果不是，l = mid + 1

反之亦然
代码如下：