首页 > 代码库 > 【leetcode】Search in Rotated Sorted Array
【leetcode】Search in Rotated Sorted Array
Search in Rotated Sorted Array
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.
利用二分法，
如果left<A[mid]，说明从左边left开始到mid是有序的
如果left>A[mid]，说明右边从mid开始，到right是有序的
如果left=A[mid]，则说明left和mid在同一个位置，如果A[mid]!=target则下一步中left=left+1;
1 class Solution { 2 public: 3 int search(int A[], int n, int target) { 4 5 int left=0; 6 int right=n-1; 7 int mid; 8 while(left<=right) 9 {10 mid=(left+right)/2;11 12 if(A[mid]==target) return mid;13 14 if(A[left]<A[mid])//left15 {16 if(A[left]<=target&&target<A[mid])17 {18 right=mid-1;19 }20 else21 {22 left=mid+1;23 }24 }25 else if(A[left]>A[mid])//right26 {27 if(A[mid]<target&&target<=A[right])28 {29 left=mid+1;30 }31 else32 {33 right=mid-1;34 }35 }36 else37 {38 //最后一个判断语句可以一起放到第一个语句里，if(A[left]<=A[mid])39 left=mid+1;40 }41 42 }43 return -1;44 }45 };
【leetcode】Search in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。