设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

Search in Rotated Sorted Array -- LeetCode

2014-03-05 09:15:00.0 LeetCode leetcode java 面试 二分查找 search  
导读:原题链接: http://oj.leetcode.com/problems/search-in-rotated-sorted-array/ 这道题是二分查找Search Insert Position的变体,看似有点麻烦,其实理清一下还是比较简单的。因为rotate的缘故,当我们切取一半的时候可能会出现误区,所以我们要做进一步的判断。具体来说,假设数组是A,每次左边缘为l,右边缘为r,还有中间位置...。。。
原题链接: http://oj.leetcode.com/problems/search-in-rotated-sorted-array/ 
这道题是二分查找Search Insert Position的变体,看似有点麻烦,其实理清一下还是比较简单的。因为rotate的缘故,当我们切取一半的时候可能会出现误区,所以我们要做进一步的判断。具体来说,假设数组是A,每次左边缘为l,右边缘为r,还有中间位置是m。在每次迭代中,分三种情况:
(1)如果target==A[m],那么m就是我们要的结果,直接返回;
(2)如果A[m]
(3)如果A[m]>=A[r],那么说明从l到m一定是有序的,同样只需要判断target是否在这个范围内,相应的移动边缘即可。

根据以上方法,每次我们都可以切掉一半的数据,所以算法的时间复杂度是O(logn),空间复杂度是O(1)。代码如下:

public int search(int[] A, int target) {    if(A==null || A.length==0)        return -1;    int l = 0;    int r = A.length-1;    while(l<=r)    {        int m = (l+r)/2;        if(target == A[m])            return m;        if(A[m]A[m] && target<=A[r])                l = m+1;            else                r = m-1;        }        else        {            if(target>=A[l] && target注意在这道题中我们假设了这个数组中不会出现重复元素。如果允许出现重复元素,那么我们要对中间和边缘的相等的情况继续处理,进而影响到时间复杂度,这个问题会在Search in Rotated Sorted Array II中具体讨论,大家有兴趣可以看看。

(编辑: linhuanmars)

网友评论