这个题和剑指 Offer 上旋转数组的题有点像,但是不一样,因为剑指 offer 明确了是一个递增排序的数组,如果我们明确了递增的话就能取到 mid,然后通过 mid 与 left 以及 right 的相对大小来判断接下来的走向,但是现在的问题是这个题没有明确。
首先分析本题要考察什么:数据结构数组,算法的是查找而且是有序数组查找。因此我们要利用这个有序,那么最合适也最常考察的就是二分了。也就是说本题本质上是考察的二分查找。二分查找最最主要的条件是
1 明确数组有序,这决定了 mid 的含义
2 明确数组是升序还是降序,这决定了 mid 接下来的走向.
只要构造出一个有序的数组,我们就能用二分了,那么问题就转变成了如何构造一个有序的数组。题目中的数组声称是有序,但是经过一些操作被打断了,那么我们只要把这个有序数组还原就好了。
于是问题就转变成了如何把这个转动的有序数组进行还原。
方法就是:直接把数组复制两边然后连接起来,那么这个新数组中间一定有一个是有序的数组。接下来问题就转变成了如何寻找这个有序数组的边界,把有序数组这部分元素挑出来。元素边界挑出来后,再根据 left 和 right 的相对大小来确定这个有序数组的方向。那么我们确定了元素,确定了方向后就可以根据二分法找到对应的元素了。
但是找到的元素的下标不一定和原来的位置重合,我们进行还原一下就好了。
经验总结:在考察数据算法的时候一般不会明白白的让你写一个原理算法出来,而是通过各种花哨的场景,让你对原理算法进行一些改写,比如这道题是属于什么?肯定是二分,但是尼首先你要先通过分析去将一些不熟悉的场景变成我们熟悉的场景,这是考察对算法的理解。然后熟悉的场景也不是对算法照搬,也要对算法进行一些改写,比如这里多了一层数组有序的方向进行判断。也就是说你在这里实现了一个有序数组的二分,不管是递增还是递减都可以用。
public int search (int[] A, int target) { // write code here if(A==null || A.length==0){ return -1; } int res=-1; if(A.length==1){ if(target==A[0]){ res=0; } }else{ int len=A.length; int [] arr=new int[2*len]; for(int i=0;i<len;i++){ arr[i]=A[i]; arr[i+len]=A[i]; } int start=-1; for(int i=1;i<len;i++){ if(arr[i]==target){ res=i; break; } if(arr[i]>arr[i+1] && arr[i]>arr[i-1]){ start=i+1; break; }else if(arr[i]<arr[i+1] && arr[i]<arr[i-1]){ start=i+1; break; } } if(res==-1){ int end=start+len-1; int targetIndex=binarySearch(arr,start,end,target); if(targetIndex!=-1){ if(targetIndex>=len){ res=targetIndex-len; }else{ res=targetIndex; } } } } return res; } public int binarySearch(int [] arr,int left ,int right,int target){ int res=-1; while(left<=right){ int mid=(left+right)/2; if(arr[mid]==target){ res=mid; break; }else{ if(arr[left]<arr[right]){ if(arr[mid]<target){ left=mid+1; }else{ right=mid-1; } }else{ if(arr[mid]<target){ right=mid-1; }else{ left=mid+1; } } } } return res; }