继续打卡算法题，今天学习的是LeetCode的第33题搜索旋转排序数组，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。
分析一波题目
这个题目在一个数组中查找一个数字，遍历一遍也可以找到,这样时间复杂度是O(n)。但是题目要求时间复杂度是O(log n)。 因此肯定不是直接遍历求解的。
需要O(log n)，我们可以使用二分查找，如果是严格有序的比较好求，但是这个有序数组是被旋转过的。
比如0124567
由于不是严格递增，二分法可能产生两种结果。
- 中间位置mid前的数据是严格递增的，这种情况和普通的二分求解一样。看目标数据在不在前半部分。
- 中间位置mid前的数据不是严格递增的，这种情况需要看目标数据在不在后半部分。
二分法的结果就是一个数字只会在左半边或者右半边
编码解决
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
//前半部分严格递增。
if (nums[0] <= nums[mid]) {
//目标数据在前半部分
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
//前半部分不是严格递增的情况
//目标数据在后半部分
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
总结
二分法在有序数组中查找某个数的情况效率是比较高的。这种非严格递增的数组也可以借助二分法解决，因此只要有顺序规律，就可以使用二分法来求解。
