给定一个循环有序数组,如 4 5 6 0 1 2 3 ,寻找其是否存在特定值,并返回其坐标。数组中不存在重复元素。
思路:要求复杂度为O(log n),则联想到二分查找,问题在于二分之后去向哪边。这里用了一个很巧妙的方法来决定去向,首先我们要关注三个数,当前搜索下界, 当前搜索中值和当前搜索上界。而显然它们也是呈现一个循环的大小。( nums[0] > target ) ^ ( nums[0] > nums[mid] ) ^ ( target > nums[mid] )
注意的是这里的过半实质上是指循环超过了mid