LeetCode题目链接链接
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回-1。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是O(logn) 级别。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3输出:-1
在做这道题之前。把时间复杂度重新理解一下
（1）O(1)：常量阶，运行时间为常量
（2）O(logn)：对数阶，如二分搜索算法
（3）O(n)：线性阶，如n个数内找最大值
（4）O(nlogn)：对数阶，如快速排序算法
（5）O(n^2)：平方阶，如选择排序，冒泡排序
（6）O(n^3)：立方阶，如两个n阶矩阵的乘法运算
（7）O(2^n)：指数阶，如n个元素集合的所有子集的算法
（8）O(n!)：阶乘阶，如n个元素全部排列的算法
对于O(logn)，可以参照下面的博客链接
[收藏]时间复杂度 O(log n) 意味着什么？ - [| 小人物，大世界 - CSDN博客
分析：
其实这道理只要找对分类情况的话，就很简单了。但是这个情况不好找。
由于数字无论这么翻转，总有一个是正序的。另外一个是乱序或者。那么如何判断是在正序或者乱序呢？整体思路是采用二分法，但是要修改二分法。
二分法
int binarysearch(int arr[],int key,int left,int right) {
//求中间元素的下标
int mid = (left + right) /2;
//数组内不含有指定元素，依据下标的规则，退出
if (left > right)
return -1;
//查找到指定元素
if (key == arr[mid]) {
return mid;
//当查找的元素大于中间下标的元素，则改变开始下标的位置
}
else if (key > arr[mid]) {
return binarysearch(arr, key, mid +1, right);
}
else {
//当查找的元素小于中间下标的元素，则改变结束下标的位置
return binarysearch(arr, key, left, mid -1);
}
}
1. 如果第一位first < mid（first为要寻找的区间的第一位，mid为要寻找区间的中间位），
如果 first < target < array[mid] 则该区间是正序
否则 target不在正序区间
2. 如果第一位first > mid
如果 first < target < array[mid] 则该区间是正序
否则 target不在正序区间
代码
class Solution {
public int search(int[] nums, int target) {
if(nums.length<=0){
return -1;
}
int first = nums[0];
if(first == target){
return 0;
}
int last = nums[nums.length-1];
if(last == target){
return nums.length-1;
}
return binarysearch(nums, 0, nums.length-1,target,first, last);
}
public static int binarysearch(int array[], int low, int high, int target,int first,int last) {
if (low > high) {
return -1;
}
if (low == high){
if (array[low] == target){
return low;
}else {
return -1;
}
}
int mid = low + (high - low) / 2;
if (target == array[mid]){
return mid;
}
if (first < array[mid]){
if (target > first && target < array[mid]){
if (array[mid-1]==target){
return mid-1;
}
return binarysearch(array, low, mid-1, target, first,array[mid-1]);
}else {
if (array[mid+1]==target){
return mid+1;
}
return binarysearch(array, mid + 1, high, target, array[mid+1], last);
}
}
if (first > array[mid] ){
if (target > array[mid] && target < last){
if (array[mid+1]==target){
return mid+1;
}
return binarysearch(array, mid + 1, high, target,array[mid+1], last);
}else {
if (array[mid-1]==target){
return mid-1;
}
return binarysearch(array, low, mid - 1, target,first, array[mid - 1]);
}
}
return -1;
}
}
结果
