[Java][BinarySearch][LeetCode] Search in Rotated Sorted Array II #81

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

This problem can use traverse or binary search. I think traverse is more intuition. Binary search explanations are under:
if nums[mid]=nums[left]: it’s meant, maybe array is include continuity. but we don’t know which zone is. so we need to shift left border and recalculate mid.
if nums[mid]<=nums[right]: it’s meant, right zone is increase order. we can done binary search in this zone.
except as stated above, it’s meant left zone is increase order.
after confirm which zone, we need to scale zone, until left>right.

這題看起來用遍歷或是二分查找做都可以，
遍歷是比較直觀的作法，從頭找到就結束了，
二分查找的部分是，
如果mid的值等於左側的值，則表示可能是連續的相同數，
但無法確定是左邊區間還是右邊區間，
於是把左邊界值右移一位，讓mid重算一次。
假如mid的值小於且等於右邊界的值，
則表示右區間是遞增排序好的序列，否則為左區間是遞增排序好的序列，
先確認是在哪邊的區間之後，
再確認是要縮減左邊界或是右邊界。