大家好，又见面了，我是全栈君。
题目
Suppose a sorted array 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.
解题思路
旋转数组中的查找。
[1, 2, 3, 4, 5, 6]的一个旋转数组为[4, 5, 6, 1, 2, 3]。在旋转数组中寻找一个数。
最直接的方法。一次遍历。时间复杂度O(n)。可是既然是一个部分有序的数组，那么对于有序的部分我们能够想方法用二分查找。这个能够提高效率。
代码实现
class Solution {
public:
int search(int A[], int n, int target) {
if(A==NULL || n<=0) return -1;
int begin = 0, end = n-1;
while(begin<=end){
int mid = begin + (end-begin)/2;
if(A[mid] == target)
return mid;
if(A[mid] > A[end]){
//前半段
if(A[begin]<=target && A[mid] > target){
//target 在 begin 和 mid-1 之间
end = mid-1;
}else{
begin = mid+1;
}
}else if(A[mid] < A[end]){
//在后半段
if(A[mid] < target && A[end] >=target){
//target 在 mid+1 和 end 之间
begin = mid+1;
}else{
end = mid-1;
}
}else{
// 由于这个题数组中不含有反复元素，此时begin==end==mid而且A[mid]!=target。所以不存在
break;
}
}
return -1;
}
};
假设你认为本篇对你有收获，请帮顶。
另外，我开通了微信公众号–分享技术之美，我会不定期的分享一些我学习的东西.
另外，我开通了微信公众号–分享技术之美，我会不定期的分享一些我学习的东西.
你能够搜索公众号：
swalge
或者扫描下方二维码关注我
swalge
或者扫描下方二维码关注我
![[LeetCode] Search in Rotated Sorted Array [35]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
（转载文章请注明出处: http://blog.csdn.net/swagle/article/details/30471141 )
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115876.html原文链接：https://javaforall.net
