SearchInRotatedSortedArray [source code]

public class SearchInRotatedSortedArray {
static
/******************************************************************************/
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target == nums[mid])
                return mid;
            if (nums[mid] < nums[lo]) {
                // 6,7,0,1,2,3,4,5
                if (target < nums[mid] || target >= nums[lo])
                    hi = mid - 1;
                else
                    lo = mid + 1;
            } else {
                // 2,3,4,5,6,7,0,1
                if (target > nums[mid] || target < nums[lo])
                    lo = mid + 1;
                else
                    hi = mid - 1;
            }
        }
        return -1;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SearchInRotatedSortedArray.Solution tester = new SearchInRotatedSortedArray.Solution();
        int[][] inputs = {
            {4,5,6,7,0,1,2}, {6}, {2},
            {4,5,6,7,0,1,2}, {5}, {1},
            {4,5,6,7,0,1,2}, {1}, {5},
            {5,1,3}, {5}, {0},  // critical positions of two == against [lo]
            {1,3,5}, {1}, {0},  // critical positions of two == against [lo]
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i];
            int target = inputs[3 * i + 1][0], ans = inputs[3 * i + 2][0];
            System.out.println (Printer.separator ());
            int output = tester.search (nums, target);
            System.out.printf ("[%s] and %d -> %s, expected: %d\n", 
                Printer.array (nums), target, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

熟悉rotate这个概念, 并不是传统意义上的invert之类的东西;

这个题目最后肯定是要一个优于O(N)的解法的;

第一个想法是这个隔断的思路, 两段都是sorted, 更重要的是, 两段其实能连起来; 立刻一个想法, 就是两个copy append起来(实际计算的时候通过index计算来实现而不是真的append, 不然就直接已经是O(N)了); 但是append的下一步是什么?

瞄到了tag, 是binary search; 还是不知道怎么做;

还是先笔算, 尤其是这种完全没有思路的题目, 那么就先随便乱花, again, 坏办法好过没办法, 就算是感觉naive的离谱的方法, 完全没把握的方法, 也可以在白板上展示: 真正面试的时候反正是要这样做的;

好像有点思路, 写写看;

最后就用上面comment里面的两个例子, 开发出来了这个思路, 关键就看你mid落在了哪一段. 这个题目还是很有意思的;

另外, 最后两个test把一开始的代码给break掉了, 就是因为这题两个branch里面的时候, ==的位置非常的关键; 可以自己跑一下这两个case就知道了; 当然了, 你也可以直接给==[lo]的情况来一个special case, 不过能一起处理掉我认为还是最elegant的;

最后速度是13ms (83%), 不丢人好吧; 虽然做题时间稍微超时了, 大概40分钟;

最后讨论一点, binary search问题当中, ==情况的临界值往往都很难处理; 在普通的binary search的时候, 我们只要处理[mid]和target的关系, 等号的处理也方便; 但是在这个题目, 你还要和[lo]进行对比, 这个对比的等号情形也不要忘记在提交之前自己脑子检查一遍, 往往是复杂的Corner Case问题;

没有editorial;

@lucastan said in Concise O(log N) Binary search solution: 

class Solution {  
public:  
    int search(int A[], int n, int target) {  
        int lo=0,hi=n-1;  
        // find the index of the smallest value using binary search.  
        // Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.  
        // Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.  
        while(lo<hi){  
            int mid=(lo+hi)/2;  
            if(A[mid]>A[hi]) lo=mid+1;  
            else hi=mid;  
        }  
        // lo==hi is the index of the smallest value and also the number of places rotated.  
        int rot=lo;  
        lo=0;hi=n-1;  
        // The usual binary search and accounting for rotation.  
        while(lo<=hi){  
            int mid=(lo+hi)/2;  
            int realmid=(mid+rot)%n;  
            if(A[realmid]==target)return realmid;  
            if(A[realmid]<target)lo=mid+1;  
            else hi=mid-1;  
        }  
        return -1;  
    }  
};

有点意思的思路, 他还是纠结于先找到rotate的点, 然后后面的就简单了; 没想到还真的让他找到了;

@renegade said in Concise O(log N) Binary search solution:

This code is much more readble: 

public class Solution {  
    public int search(int[] nums, int target) {  
        int start = 0, end = nums.length - 1;  
        while (start < end) {  
            int mid = (start + end) / 2;  
            if (nums[mid] > nums[end]) {  // eg. 3,4,5,6,1,2  
                if (target > nums[mid] || target <= nums[end]) {  
                    start = mid + 1;  
                } else {  
                    end = mid;  
                }  
            } else {  // eg. 5,6,1,2,3,4  
                if (target > nums[mid] && target <= nums[end]) {  
                    start = mid + 1;  
                } else {  
                    end = mid;  
                }  
            }  
        }  
        if (start == end && target != nums[start]) return -1;  
        return start;  
    }  
}

这个就是跟我的做法是非常类似的; 正好顺手重新看了一下他的代码, 发现这个算法当时开发的时候感觉很复杂, 最后实际出来的算法是相当intuitive的; binary search, 一个核心的问题就是: which direction of MID to go. 然后你举好例子, 看看什么情况下往那个方向走就行了; 当然了, 真正当时做题目的时候肯定不能用这么抽象的东西来指导思考, 但是如果大概的思路有了之后, 适当提醒一下自己这种rule of thumb, 可以让写代码的速度快很多;

这个是针对一开始的OP的:

@EXLsunshine said in Concise O(log N) Binary search solution:

I think the second while loop can be optimised. Given that you have already known the left hand sub array and the right hand sub array, so we don't have to set low = 0 and high = n - 1, we can set the arrange more precisely to [0 - smallest_index] or smallest_index, high. Am I right?

这时候我才发现原来的OP的做法的毛病: 他第二个循环确实是搞得太复杂了; 当然, 他的想法是好的: 知道了rotate的位置, 就相当于让所有的index有了一个offset(向右). 然后后面计算的时候用的是类似我的append 2 copies的思路; 不过这个确实是多余的. 我当时看完了他的第一个循环, 就直接认为应该是直接按照这个评论这里描述的这个方法做就行了(实际上相当于binary search的第一段不是完全的balanced, 而是手动选择).

关于append:

@lavender_sz said in Concise O(log N) Binary search solution:

For those who struggled to figure out why it is realmid=(mid+rot)%n: you can think of it this way:
If we want to find realmid for array [4,5,6,7,0,1,2], you can shift the part before the rotating point to the end of the array (after 2) so that the sorted array is "recovered" from the rotating point but only longer, like this: [4, 5, 6, 7, 0, 1, 2, 4, 5, 6, 7]. The real mid in this longer array is the middle point between the rotating point and the last element: (rot + (hi+rot)) / 2. (hi + rot) is the index of the last element. And of course, this result is larger than the real middle. So you just need to wrap around and get the remainder: ((rot + (hi + rot)) / 2) % n. And this expression is effectively (rot + hi/2) % n, which is (rot+mid) % n.
Hope it helps!

当然, 我是知道的就是了;

@jerry13466 said in Revised Binary Search: 

public class Solution {  
    public int search(int[] A, int target) {  
        int lo = 0;  
        int hi = A.length - 1;  
        while (lo < hi) {  
            int mid = (lo + hi) / 2;  
            if (A[mid] == target) return mid;  

            if (A[lo] <= A[mid]) {  
                if (target >= A[lo] && target < A[mid]) {  
                    hi = mid - 1;  
                } else {  
                    lo = mid + 1;  
                }  
            } else {  
                if (target > A[mid] && target <= A[hi]) {  
                    lo = mid + 1;  
                } else {  
                    hi = mid - 1;  
                }  
            }  
        }  
        return A[lo] == target ? lo : -1;  
    }  
}

还是我这个方法. 最后一行的这个判断感觉没必要, 他中间hit用的是return又不是break; 能hit, 早就return了;

@mo10 said in Revised Binary Search:

If you change your while condition to lo<=hi, then you will simply need to return just -1 in the end.

哦, 看来是因为他用的是开区间的原因. 所以闭区间还是普适性更强的写法;

作者自己对于思路的解释:

@jerry13466 said in Revised Binary Search:

Notice that there is always a half of the array sorted, so we only need to see whether the target is in the sorted part or rotated part

虽然我自己开发的时候并没有考虑这个问题; 我自己这题能做出来, 很大一个原因就是笔头子动的狠, 什么刚开始觉得简直是狗屁的思路都去尝试一下, 突然就有了正确的灵感. 我还是强调一下, 坏办法好过没办法. 甚至是, 很多时候你是一点思路都没有的, 包括人逻辑都没有, 这个时候你怎么办? 就好像我上次contest: global and local conversion那一题, 这个时候你就适当的猜. 事实上, 那题我当时做出来的解法我到现在都不会证明. 但是这总好过你没做出来, 是吧?

这个帖子下面看来, 好多人对于开区间和闭区间的写法, 也是不够熟悉, 各种不理解edge case; 还好我夏天当时狠心稍微总结了一下, 不敢说现在特别熟练, 但是至少不担心写一个不能terminate的binary search. 另外再次强调, invariant and its corresponding (closed) interval.

@flyinghx61 said in Java AC Solution using once binary search:

The idea is that when rotating the array, there must be one half of the array that is still in sorted order.
For example, 6 7 1 2 3 4 5, the order is disrupted from the point between 7 and 1. So when doing binary search, we can make a judgement that which part is ordered and whether the target is in that range, if yes, continue the search in that half, if not continue in the other half. 

public class Solution {  
    public int search(int[] nums, int target) {  
        int start = 0;  
        int end = nums.length - 1;  
        while (start <= end){  
            int mid = (start + end) / 2;  
            if (nums[mid] == target)  
                return mid;  

            if (nums[start] <= nums[mid]){  
                 if (target < nums[mid] && target >= nums[start])   
                    end = mid - 1;  
                 else  
                    start = mid + 1;  
            }   

            if (nums[mid] <= nums[end]){  
                if (target > nums[mid] && target <= nums[end])  
                    start = mid + 1;  
                 else  
                    end = mid - 1;  
            }  
        }  
        return -1;  
    }  
}

again, binary search就是要把注意力放在mid, 以及mid的下一步; 所以不要被两个sorted分段之间的分区, mid的位置才是更relevant;

这个有意思, 一个人发了帖子:

@rantos22 said in C++ 4 lines 4ms: 

    int search(vector<int>& nums, int target)   
    {  
            auto skip_left  = [&]( int x) { return x >= nums[0] ? numeric_limits<int>::min() : x; };  
            auto skip_right = [&] (int x) { return x < nums[0] ? numeric_limits<int>::max() : x; };  
            auto adjust = [&] (int x) { return target < nums[0] ? skip_left(x) : skip_right(x); };  

            auto it = lower_bound( nums.begin(), nums.end(), target, [&] (int x, int y) { return adjust(x) < adjust(y); } );  

            return it != nums.end() && *it == target ? it-nums.begin() : -1;  
    }

You are not expected to understand that :)

这个就很装逼了, 然后Stefan看到了, 当天写了一个帖子给解释出来了:

@StefanPochmann said in Clever idea making it simple:

This very nice idea is from rantos22's solution who sadly only commented "You are not expected to understand that :)", which I guess is the reason it's now it's hidden among the most downvoted solutions. I present an explanation and a more usual implementation.

Explanation

Let's say nums looks like this: [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Because it's not fully sorted, we can't do normal binary search. But here comes the trick:

  • If target is let's say 14, then we adjust nums to this, where "inf" means infinity:
    [12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

  • If target is let's say 7, then we adjust nums to this:
    [-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

And then we can simply do ordinary binary search.

Of course we don't actually adjust the whole array but instead adjust only on the fly only the elements we look at. And the adjustment is done by comparing both the target and the actual element against nums[0].

Code

If nums[mid] and target are "on the same side" of nums[0], we just take nums[mid]. Otherwise we use -infinity or +infinity as needed. 

    int search(vector<int>& nums, int target) {  
        int lo = 0, hi = nums.size();  
        while (lo < hi) {  
            int mid = (lo + hi) / 2;  

            double num = (nums[mid] < nums[0]) == (target < nums[0])  
                       ? nums[mid]  
                       : target < nums[0] ? -INFINITY : INFINITY;  

            if (num < target)  
                lo = mid + 1;  
            else if (num > target)  
                hi = mid;  
            else  
                return mid;  
        }  
        return -1;  
    }

其实跟我的算法的思路是差不多的, 都是跟[lo]对比, 因为他是分界线; 不过这里这个思路看起来更slick而已; 注意看, 他这里把[0]看成一个pivot, 每一个iteration都是跟[0]对比, 而不是[lo].

原来的作者的做法好像其实是没有使用binary search的, 不过Stefan这里的改写是用了的; //不对, 后面别的帖子看到, lower_bound好像是lgN的复杂度的;

@jialiang.wang.75 said in Clever idea making it simple:

It can be a follow up of find minimum in rotated array -:)

这个不知道想表达什么, 如果是找最值, 那么直接用discussion第一个解法的那个写法就可以了;

一个类似的变形:

@lester.neo.leon said in Clever idea making it simple:

Inspired by this and @StefanPochmann work here: https://discuss.leetcode.com/topic/34467/pretty-short-c-java-ruby-python

We can also view the array as already sorted with the following transformation: 

tuple: (value less than nums[0]?, value)  
[1,2,3,4,5] -> [(0,1), (0,2), (0,3), (0,4), (0,5)]  
[5,1,2,3,4] -> [(0,5), (1,1), (1,2), (1,3), (1,4)]

Then we can use our standard binary search like so: 

    def search(self, nums, target):  
        N, t = nums, target  
        i = bisect.bisect_left([(x < N[0], x) for x in N], (t < N[0], t))  
        return i if t in N[i:i+1] else -1

But that's already O(n) for the transform so ...: 

    def search(self, nums, target):  
        lo, hi, t = 0, len(nums) - 1, (target < nums[0], target)  
        while lo <= hi:  
            mid = (lo + hi) // 2  
            guess = (nums[mid] < nums[0], nums[mid])  
            if   guess == t: return mid  
            elif guess < t:  lo = mid + 1  
            else:            hi = mid - 1  
        return -1

之前好像也碰到过这种做法, 好像是在一个有duplicate的题目里面, 用一个类似的额外的数字来augment这个element; 不过这里的实际上的这个做法比较定制化, 这里augment的实际上是一个类似flag的东西;

顺手, Stefan的另外一个解法:

@StefanPochmann said in Pretty short C++/Java/Ruby/Python:

Explanation below the codes.

Ruby: 

def search(nums, target)  
  i = (0...nums.size).bsearch { |i|  
    (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])  
  }  
  nums[i || 0] == target ? i : -1  
end

Ruby Golf, just once for fun: 

def search(n, t)  
  i=(0...n.size).bsearch{|i|(n[0]<=t)^(n[0]>n[i])^(t>n[i])};n[i||0]==t ?i:-1  
end

Python: 

def search(self, nums, target):  
    lo, hi = 0, len(nums) - 1  
    while lo < hi:  
        mid = (lo + hi) / 2  
        if (nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]):  
            lo = mid + 1  
        else:  
            hi = mid  
    return lo if target in nums[lo:lo+1] else -1

Python using bisect: 

class Solution:  
    def search(self, nums, target):  
        self.__getitem__ = lambda i: \  
            (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])  
        i = bisect.bisect_left(self, True, 0, len(nums))  
        return i if target in nums[i:i+1] else -1

C++: 

int search(vector<int>& nums, int target) {  
    int lo = 0, hi = int(nums.size()) - 1;  
    while (lo < hi) {  
        int mid = (lo + hi) / 2;  
        if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))  
            lo = mid + 1;  
        else  
            hi = mid;  
    }  
    return lo == hi && nums[lo] == target ? lo : -1;  
}

Java: 

public int search(int[] nums, int target) {  
    int lo = 0, hi = nums.length - 1;  
    while (lo < hi) {  
        int mid = (lo + hi) / 2;  
        if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))  
            lo = mid + 1;  
        else  
            hi = mid;  
    }  
    return lo == hi && nums[lo] == target ? lo : -1;  
}

Explanation

My solutions use binary search guided by the following thoughts:

Remember the array is sorted, except it might drop at one point.

  • If nums[0] <= nums[i], then nums[0..i] is sorted (in case of "==" it's just one element, and in case of "<" there must be a drop elsewhere). So we should keep searching in nums[0..i] if the target lies in this sorted range, i.e., if nums[0] <= target <= nums[i].

  • If nums[i] < nums[0], then nums[0..i] contains a drop, and thus nums[i+1..end] is sorted and lies strictly between nums[i] and nums[0]. So we should keep searching in nums[0..i] if the target doesn't lie strictly between them, i.e., if target <= nums[i] < nums[0] or nums[i] < nums[0] <= target

Those three cases look cyclic: 

    nums[0] <= target <= nums[i]  
               target <= nums[i] < nums[0]  
                         nums[i] < nums[0] <= target

So I have the three checks (nums[0] <= target), (target <= nums[i]) and (nums[i] < nums[0]), and I want to know whether exactly two of them are true. They can't all be true or all be false (check it), so I just need to distinguish between "two true" and "one true". Parity is enough for that, so instead of adding them I xor them, which is a bit shorter and particularly helpful in Java and Ruby, because those don't let me add booleans but do let me xor them.

(Actually while developing this I thought of permutations of nums[0], target and nums[i] and the permutation parity and saw those three checks as representing inversions, but I had trouble putting that into words and now find the above explanation much better. But it helped me get there, so I wanted to mention it here.)

最下面的这个解释还是有点聪明的, 不过也是看出来这个人为了节省代码量真的已经有点走火入魔了;

submission基本波动;

Problem Description

Suppose an array sorted in ascending order 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.

Difficulty:Medium
Total Accepted:230.3K
Total Submissions:718.5K
Contributor:LeetCode
Companies
facebookmicrosoftbloomberguberlinkedin
Related Topics
arraybinary search
Similar Questions
Search in Rotated Sorted Array IIFind Minimum in Rotated Sorted Array

results matching ""

    No results matching ""