81. 搜索旋转排序数组 II

在经过一次旋转的有序数组中寻找给定值，并且数组中可能有重复元素。这里的难点在于可能有重复元素，导致旋转点位置的判断变得困难。如果没有重复元素，那么只需去比较left, mid, right三个位置的值，就能确定旋转点在哪个半边。

思路

1. 尝试寻找旋转点

首先，要尝试在这个数组中寻找旋转点，将整个数组分为左右半边，然后判断:

1. 是否能确定旋转点在左半边？
2. 是否能确定旋转点在右半边？
3. 如果既不能确定在左半边/右半边，那么l++。

如何确定旋转点？记住一个窍门: 区间两端出现逆序时，代表旋转点在区间内部。
当nums[left] > nums[mid]时，一定旋转点在左半边，为什么呢？因为左半边出现了逆序，那么左侧至少有一个旋转点。而数组中至多有一个旋转点，所以右侧一定是顺序的。

同理，当nums[mid] > nums[right]时，一定旋转点在右半边。

为什么只有当出现端点与中点的逆序时，才能确定旋转点坐在半区？因为只有出现逆序，才能确定该区间有旋转点，如果