33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] ).
You are given a target value to search. If found in the array return its index, otherwise return -1 .
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O (log n ).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [ 4,5,6,7,0,1,2] , target = 3
Output: -1
/* 掌握
问题：在旋转数组中查找（不存在重复数字）
方法：二分查找，先找有序范围，再判断有序范围内有没有，更新 left 或 right 指针，不断缩小范围
O(logn)
*/
class Solution
{
public :
int search ( vector < int >& a , int target )
{
if ( a . empty ()) return - 1 ;
int left = 0 , right = a . size () - 1 ;
while ( left <= right )
{
int mid = ( left + right ) / 2 ;
if ( a [ mid ] == target )
return mid ;
else if ( a [ mid ] < a [ right ]) // 若中间数小于最右边的数，则右半段（ mid~right ）是有序的
{
if ( target > a [ mid ] && target <= a [ right ]) // 在有序的半段里用首尾两个数来判断目标值是否在这一区域内
left = mid + 1 ; // 说明在 mid~right 内，更新 left 位置
else
right = mid - 1 ;
}
else // 若中间数大于最右边的数，则左半段 (left~mid) 是有序的
{
if ( target >= a [ left ] && target < a [ mid ]) // 由于判断下来不可能有 target = a[mid] ，故这里没有取等号
right = mid - 1 ; // 说明在 left~mid 内，更新 right 位置
else
left = mid + 1 ;
}
}
return - 1 ;
}
};
//此方法技巧性较高，了解即可
//方法：二分查找（因为有O(logn)的限制）
class Solution
{
public :
int search ( vector < int >& a , int target )
{
if ( a . empty ()) return - 1 ; //特殊情况：空数组
//使用二分查找找到最小值的索引（旋转的地方）
//旋转之后左半边数组比右半边数组大，通过二分查找，找到分界点（最小值）即可，最小值在左半数组最末尾，右半数组起始位置
int n = a . size ();
int left = 0 , right = n - 1 ;
int indexmin = 0 ; //初始化最小值的位置
while ( a [ left ] > a [ right ]) //特殊情况：输入有序数组，可以看成rotate 0，则直接退出循环，indexmin用初始值0
{
int mid = ( left + right )/ 2 ;
if ( a [ mid ]> a [ right ]) left = mid ; //a[mid]>a[right]说明mid在左半边数组，将left指针移至mid
else right = mid ; //a[mid]<a[right]说明mid在右半边数组，将right指针移至mid
if ( right - left == 1 )
{
indexmin = right ; break ; //跳出循环
}
} //循环结束后left指向左半数组末尾，right指向右半数组开头
//找序列中的极小值（联系find peak element这题）
left = 0 ; right = n - 1 ;
//使用常规的二分查找(对于增序序列而言)，并考虑旋转
while ( left <= right )
{
int mid = ( left + right )/ 2 ;
int realmid = ( mid + indexmin )% n ; //indexmin为数组中最小数的位置（本来为0位置，现在变为rot位置），相当于附加偏移以找到真正的mid位置
if ( a [ realmid ] < target ) left = mid + 1 ;
else if ( a [ realmid ] > target ) right = mid - 1 ;
else return realmid ;
}
return - 1 ; //未找到
}
};
81 . Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2] ).
You are given a target value to search. If found in the array return true , otherwise return false .
Example 1:
Input: nums = [2 ,5,6,0,0,1,2] , target = 0
Output: true
Example 2:
Input: nums = [2 ,5,6,0,0,1,2] , target = 3
Output: false
Follow up:
- This is a follow up problem to , where nums may contain duplicates.
- Would this affect the run-time complexity? How and why?
/*
问题：在旋转数组中查找 2 （可以存在重复数字）
方法：二分查找，先找有序范围，再判断有序范围内有没有，更新 left 或 right 指针，不断缩小范围
如果 a[mid] 与 a[right] 相等，则让 right-- 直到不相等，其余部分与问题 Search in Rotated Sorted Array I 相同
O(logn)
*/
class Solution
{
public :
bool search ( vector < int >& a , int target )
{
if ( a . empty ()) return false ;
int left = 0 , right = a . size () - 1 ;
while ( left <= right )
{
int mid = ( left + right ) / 2 ;
if ( a [ mid ] == target )
return true ;
else if ( a [ mid ] < a [ right ]) // 若中间数小于最右边的数，则右半段（ mid~right ）是有序的
{
if ( target > a [ mid ] && target <= a [ right ]) // 在有序的半段里用首尾两个数来判断目标值是否在这一区域内
left = mid + 1 ; // 说明在 mid~right 内，更新 left 位置
else
right = mid - 1 ;
}
else if ( a [ mid ] > a [ right ]) // 若中间数大于最右边的数，则左半段 (left~mid) 是有序的
{
if ( target >= a [ left ] && target < a [ mid ]) // 由于判断下来不可能有 target = a[mid] ，故这里没有取等号
right = mid - 1 ; // 说明在 left~mid 内，更新 right 位置
else
left = mid + 1 ;
}
else //若中间数等于最右边数，移动right指针
right --;
}
return false ;
}
};