升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。
请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- nums 中的每个值都 独一无二
- nums 肯定会在某个点上旋转
- -10^4 <= target <= 10^4
这个题目本身题意并不难理解,就是如何在一个数组中查找一个元素。但难度定义为中等难度,所以,如果写一个复杂度为O(n)的顺序查找肯定是不ok的了。我们应该考虑使用一个复杂度比O(n)还低的查找算法,比如,二分查找。
二分查找,是一种在有序数组上查找元素的方法,其要求就是,数组是有序的。
那对于上面这个题目,本来是有序数组,做了旋转后,整个数组就不是有序的了。那怎么使用二分查找呢?
原数组是有序的,从某个元素旋转后,其中肯定有一半是有序的,比如[4,5,6,7,8,0,1,2],总共7个元素,我们将数组一分为二,[4,5,6,7]和[8,0,1,2],其中前半部分[4,5,6,7]是有序的,这样我们就可以在这部分有序的数组上进行二分查找。
那后半部分还是无序的,如果要查找的元素在后半部分怎么办呢?仔细看,后半部分虽然是无序的,但和整个数组性质是一样的,也算是一个有序数组的旋转数组,我们再将后半部分一分为二,其中有一半肯定是有序的。
所以,到这里问题就明朗了,我们的大致解题步骤如下:
- 先找到升序区间
- 如果元素在升序区间内,直接在升序区间对其进行二分查找
- 如果元素不在升序区间内,那么我们再对剩下的非升序区间进行步骤1操作。
- 找到元素或区间缩小至只有一个元素时结束查找。
1 | func binarySearch(nums []int, start, end int, target int) int { |