排序数组在旋转后,可以分为前后两个排序子序列。在没有相同元素的情况下,前一个数组中的元素均大于后一个数组中的元素。
如果我们要找最小元素,则只要找到两个数组的分界点即可,即第二个子序列的开始元素。
由于子序列分别有序,所以我们可以采用二分查找的思想来解决问题,不断缩小查询范围。
这道题要注意特例情况:
1.数组中只有一个元素
2.把排序数组前面的0个元素搬到最后面,即排序数组本身,这仍然是一个数组的旋转
3.如果数组中含有相同的元素,则情况更为复杂。此时用二分查找不太合适,要考虑使用顺序查找。
int findMin(vector & nums) { int l=0,r=nums.size()-1; if(nums.size()==0) return -1; if(nums[l]