必会算法：在旋转有序的数组中搜索
##题目
整数数组 nums 按升序排列，数组中的值互不相同
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]
关于这段描述还有另外一种说法：
将数组第一个元素挪到最后的操作，称之为一次旋转
现将nums进行了若干次旋转
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
##解题思路1
简单粗暴：遍历
这种方法很容易想到和实现
最好的情况在遍历第一个元素的时候就能找到
时间复杂度为O(1)
最差的情况是遍历到最后一个元素才能找到
时间复杂度是O(n)
所以算法：
时间复杂度：O(n)
空间复杂度：O(1)
##代码实现1
/**
* 暴力破解法
*
* @param num 给定的旋转后数组
* @param target 目标值
* @return 查询结果
*/
public static int getIndex(int[] num, int target) {
if (num == null || num.length == 0) {
return -1;
}
for (int i = 0; i < num.length; i++) {
if (num[i] == target) {
return i;
}
}
return -1;
}
时间复杂度：O(n)
空间复杂度：O(1)
##解题思路2
还是那句话
凡是看到有序或者局部有序的数组查找问题
第一个想到的就应该是用二分法试试
下面我们来分析一下
一个增序的数组是这样的
旋转n次之后就是这样的
所以我们的目标就是在这样的数组里边找目标值
可以非常清晰的看到
第二段的所有值都是小于第一段的值
这样思路就非常清晰了
在二分查找的时候可以很容易判断出
当前的中位数是在第一段还是第二段中
最终问题会简化为在一个增序数据中的普通二分查找
我们用数组[1,2,3,4,5,6,7,8,9]举例说明
target目标值为7
3次旋转之后是这个样子
使用二分查找的话，首先还是先找到中位数
即下表为(0+8)/2=4
nums[4] = 8
此时8>nums[start=0]=4的
同时8>target=7
所以可以判断出
此时mid=4是处在第一段中的
而且目标值在mid=4的前边
此时，查找就简化为了在增序数据中的查找了
以此类推还有其他四种情况： mid值在第一段，且在目标值的前边 mid值在第二段，且在目标值的前边 mid值在第二段，且在目标值的后边 mid值就是目标值
##代码实现2
套用二分查找的通用公式
代码实现如下
public static int getIndex(int[] num, int target) {
if (num == null || num.length == 0) {
return -1;
}
int start = 0;
int end = num.length - 1;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (num[mid] == target) {
return mid;
}
if (num[mid] > num[start]) {
if (target <= num[mid] && num[start] <= target) {
end = mid;
} else {
start = mid;
}
} else {
if (target >= num[mid] && target <= num[end]) {
start = mid;
} else {
end = mid;
}
}
}
if (num[start] == target) {
return start;
}
if (num[end] == target) {
return end;
}
return -1;
}
时间复杂度：O(logn)
空间复杂度：O(1)
##运行测试
时间和空间复杂度都是棒棒的
文/戴先生@2022年07月08日
---end---
更多精彩推荐