首页 > 代码库 > LeetCode: Search in Rotated Sorted Array [032]
LeetCode: Search in Rotated Sorted Array [032]
【题目】
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.
【题意】
给定一个有序的反转过的数组。这个数组的第一个值比最后一个值要大。
所给数组中没有重复元素。
【思路】
第一个值和最后一个值是反转的边界。二分查找,根据第一个值和最后一个值确定target是在哪个区域
【代码】
class Solution { public: int search(int A[], int n, int target) { if(n==0)return -1; if(A[0]<A[n-1]){ //数组未发生反转,正常的二分查找 int low=0, high=n-1; while(low<=high){ int mid=(low+high)/2; if(A[mid]==target)return mid; else if(target<A[mid])high=mid-1; else low=mid+1; } } else{ //数组未发生反转 int low=0, high=n-1; while(low<=high){ int mid=(low+high)/2; if(A[mid]==target)return mid; else if(target>A[mid]){ //先判断的位置,在确定target的位置 if(A[mid]>=A[0])low=mid+1; else if(A[mid]<=A[n-1]){ if(target<=A[n-1])low=mid+1; else if(target>=A[0])high=mid-1; else break; } else break; } else{ //先判断的位置,在确定target的位置 if(A[mid]<=A[n-1])high=mid-1; else if(A[mid]>=A[0]){ if(target>=A[0])high=mid-1; else if(target<=A[n-1])low=mid+1; else break; } else break; } } } return -1; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。