首页 > 代码库 > 【Leetcode】Search in Rotated Sorted Array
【Leetcode】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.
排序的数组查找可以采用二分查找的方法~，有序数组被转动后依然可以采用二分的思想，但是要考虑到start，end与mid的大小决定递归调用二分还是自身。
因为分治后的数组一半严格有序，一半有序的转动数组。
1st （7 tries）
class Solution {public: int search(int A[], int n, int target) { // Note: The Solution object is instantiated only once and is reused by each test case. if(A[0]<A[n-1]) return orderfind(A,0,n-1,target); else return find(A,0,n-1,target); } int find(int A[],int start,int end,int target) { if(start > end||end < start) { return -1; } int mid = (start + end)/2; if(target == A[mid]) { return mid; } else if(target > A[mid]) { if(A[mid] > A[start]) return find(A,mid+1,end,target); else if(A[mid] == A[start]) return find(A,mid+1,end,target); else { if(target == A[start]) return start; else if(target > A[start]) return find(A,start,mid-1,target); else return orderfind(A,mid+1,end,target); } } else { if(A[mid] < A[start]) return find(A,start,mid-1,target); else if(A[mid] == A[start]) return find(A,mid+1,end,target); else { if(target == A[start]) return start; else if(target > A[start]) return orderfind(A,start,mid-1,target); else return find(A,mid+1,end,target); } } } int orderfind(int A[],int start,int end,int target) { if(start > end||end < start) { return -1; } int mid = (start + end)/2; if(target == A[mid]) { return mid; } else if(target > A[mid]) { return orderfind(A,mid+1,end,target); } else { return orderfind(A,start,mid-1,target); } }};
2nd （2 tries）
class Solution {public: int search(int A[], int n, int target) { return search(A,0,n-1,target); } int search(int A[], int start, int end, int target) { if(start > end) return -1; int mid = start + (end - start)/2; //rotate n if(A[start] <= A[end]) return bsearch(A,start,end,target); if(A[mid] == target) return mid; else if(A[mid] > target) { if(A[mid] >= A[start]) { if(A[start] > target) return search(A,mid+1,end,target); else return bsearch(A,start,mid-1,target); } else { return search(A,start,mid-1,target); } } else { if(A[mid] >= A[start]) { return search(A,mid+1,end,target); } else { if(target > A[end]) { return search(A,start,mid-1,target); } else { return bsearch(A,mid+1,end,target); } } } } int bsearch(int A[], int start, int end,int target) { while(start <= end) { int mid = start + (end - start)/2; if(A[mid] == target) return mid; else if(A[mid] > target) end = mid-1; else start = mid+1; } return -1; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。