SearchForARange [source code]

public class SearchForARange {
static
/******************************************************************************/
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0)
            return new int[] {-1, -1};
        int begin = search (nums, target, true), end = search (nums, target, false);
        return begin < nums.length && nums[begin] == target ?
            new int[] {begin, end - 1} :
            new int[] {-1, -1};
    }

    public int search (int[] nums, int target, boolean go_left) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target == nums[mid]) {
                if (go_left)
                    hi = mid - 1;
                else
                    lo = mid + 1;
            } else if (target < nums[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return lo;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SearchForARange.Solution tester = new SearchForARange.Solution();
        int[][] inputs = {
            {5, 7, 7, 8, 8, 10}, {8}, {3, 4},
            {}, {0}, {-1, -1},
            {2, 2}, {3}, {-1, -1},
            {0,1,2,2,2}, {2}, {2, 4},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i], ans = inputs[3 * i + 2];
            int target = inputs[3 * i + 1][0];
            System.out.println (Printer.separator ());
            int[] output = tester.searchRange (nums, target);
            String output_str = Printer.array (output), ans_str = Printer.array (ans);
            System.out.printf ("[%s] and %d -> %s, expected: [%s]\n", 
                Printer.array (nums), target, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
            );
        }
    }
}

先直接研究题目给的这个例子, 在研究的过程中如果感觉这个例子不是特别适合开发, 再考虑自己稍微变形一下例子;

先随便大概研究一下binary search到底会干什么:

7 < 8   ->  
8 >= 8  <-  
8 >= 8  <-

不小心写出来的就是普通的binary search; 可以看到, 普通的binary search返回的, 在有duplicate的情况下, 其实是leftmost occurrence;

三分地的时候, 大概看到一个观点:

binary search的三叉写法一般是为了找点, 二叉写法一般是为了找一个区间;

这题实际上找的就是一个类似区间的概念; 尝试写一下;

果然上面这个总结是对的, 用二叉的binary search, 可以找到这里的leftmost和rightmost(exclusive)两个点, 然后就好处理了. 最后的速度是7ms (59%);

注意test3, 这里告诉你, 你begin算出来, 实际上是可能超界的, 所以你最后主函数返回那里要加一个对index的bound的check;

看完一些discussion的解法, 才回过头来想我自己当时到底是怎么想的. 好像我当时基本主要就是想到了二叉找range, 然后笔算例子试了一下, 就做出来了; 但是看完discussion, 我可以这样理解我这里的定义, 当go_left是true的时候, 我的helper实际上是find first greater or equal. 当FALSE的时候, 是find first greater.

我的写法实际上是闭区间二叉, 感觉证明起来并不如discussion大部分的开区间二叉(hi = mid)好证明. 因为Sedgwick这种二叉写法, 实际上是容易出现一个回头的操作的, 比如你看我这里给的这个test4, 你笔算一下就知道了, 在go_left的情况下, 是会走到[0,1], 然后最后又回头到[2,1]的; 这个东西你用invariant什么的就不是很好解释;

感觉我这个写法简直无法用declarative的方法去理解, 拿go_left的情况来距离, 唯一的分析方式就是假如有一个长度为k的target的run, 那么当我们hit到当中的任何一个target的时候, 我们会往左走. 最后假如是一个长度为1的区间, 肯定停顿在run正好之前的那个element位置, 然后下一个terminate(出界)的iteration, lo正好就指向leftmost target.

纯粹的declaratively的用invariant来理解, 感觉根本讲不通: 碰到==的时候你直接向左, 这能代表什么invariant?

editorial

Approach #1 Linear Scan [Accepted]

略.

Approach #2 Binary Search [Accepted]

Intuition

Because the array is sorted, we can use binary search to locate the left and rightmost indices.

Algorithm

The overall algorithm works fairly similarly to the linear scan approach, except for the subroutine used to find the left and rightmost indices themselves. Here, we use a modified binary search to search a sorted array, with a few minor adjustments. First, because we are locating the leftmost (or rightmost) index containing target (rather than returning true iff we find target), the algorithm does not terminate as soon as we find a match. Instead, we continue to search until lo == hi and they contain some index at which target can be found.

The other change is the introduction of the left parameter, which is a boolean indicating what to do in the event that target == nums[mid]; if left is true, then we "recurse" on the left subarray on ties. Otherwise, we go right. To see why this is correct, consider the situation where we find target at index i. The leftmost target cannot occur at any index greater than i, so we never need to consider the right subarray. The same argument applies to the rightmost index.

The first animation below shows the process for finding the leftmost index, and the second shows the process for finding the index right of the rightmost index.

这个解释的很好, 思路讲的很清楚; 这题tricky的地方就是知道怎么处理hit;

class Solution {  
    // returns leftmost (or rightmost) index at which `target` should be  
    // inserted in sorted array `nums` via binary search.  
    private int extremeInsertionIndex(int[] nums, int target, boolean left) {  
        int lo = 0;  
        int hi = nums.length;  

        while (lo < hi) {  
            int mid = (lo+hi)/2;  
            if (nums[mid] > target || (left && target == nums[mid])) {  
                hi = mid;  
            }  
            else {  
                lo = mid+1;  
            }  
        }  

        return lo;  
    }  

    public int[] searchRange(int[] nums, int target) {  
        int[] targetRange = {-1, -1};  

        int leftIdx = extremeInsertionIndex(nums, target, true);  

        // assert that `leftIdx` is within the array bounds and that `target`  
        // is actually in `nums`.  
        if (leftIdx == nums.length || nums[leftIdx] != target) {  
            return targetRange;  
        }  

        targetRange[0] = leftIdx;  
        targetRange[1] = extremeInsertionIndex(nums, target, false)-1;  

        return targetRange;  
    }  
}

总体写法是类似的, 他的helper写的比我简练一些;

@stellari said in Clean iterative solution with two binary searches (with explanation):

The problem can be simply broken down as two binary searches for the begining and end of the range, respectively:

First let's find the left boundary of the range. We initialize the range to [i=0, j=n-1]. In each step, calculate the middle element [mid = (i+j)/2]. Now according to the relative value of A[mid] to target, there are three possibilities:

If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration)

If A[mid] > target, it means the range must begins on the left of mid (j = mid-1)

If A[mid] = target, then the range must begins on the left of or at mid (j= mid)

Since we would move the search range to the same side for case 2 and 3, we might as well merge them as one single case so that less code is needed:

2*. If A[mid] >= target, j = mid;

Surprisingly, 1 and 2* are the only logic you need to put in loop while (i < j). When the while loop terminates, the value of i/j is where the start of the range is. Why?

我之前自己总结binary search的时候也有过类似的结论, 最终始终都能找到一个长度为2的区间; 但是你看下面, 跟我不同的地方在于, 我当时这个思路只是用来证明, 他则是直接用来帮助实现: 他写binary search的习惯就是始终保持最后停顿在一个长度为1的区间上面, 而不是用Sedgwick写法那种, 用超界来terminate;

No matter what the sequence originally is, as we narrow down the search range, eventually we will be at a situation where there are only two elements in the search range. Suppose our target is 5, then we have only 7 possible cases:
case 1: [5 7] (A[i] = target < A[j])  
case 2: [5 3] (A[i] = target > A[j])
case 3: [5 5] (A[i] = target = A[j])
case 4: [3 5] (A[j] = target > A[i])
case 5: [3 7] (A[i] < target < A[j])
case 6: [3 4] (A[i] < A[j] < target)
case 7: [6 7] (target < A[i] < A[j])

For case 1, 2 and 3, if we follow the above rule, since mid = i => A[mid] = target in these cases, then we would set j = mid. Now the loop terminates and i and j both point to the first 5.

For case 4, since A[mid] < target, then set i = mid+1. The loop terminates and both i and j point to 5.

For all other cases, by the time the loop terminates, A[i] is not equal to 5. So we can easily know 5 is not in the sequence if the comparison fails.

这个枚举的方法我分析binary search的时候好像也用到过;

不过这个人的语言组织真的是非常混乱的, 如果不是我之前自己总结过, 真的不知道他这里到底想表达什么;

In conclusion, when the loop terminates, if A[i]==target, then i is the left boundary of the range; otherwise, just return -1;

For the right of the range, we can use a similar idea. Again we can come up with several rules:

If A[mid] > target, then the range must begins on the left of mid (j = mid-1)

If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration)

If A[mid] = target, then the range must begins on the right of or at mid (i= mid)

Again, we can merge condition 2 and 3 into:
2* If A[mid] <= target, then i = mid;  
However, the terminate condition on longer works this time. Consider the following case:
[5 7], target = 5  
Now A[mid] = 5, then according to rule 2, we set i = mid. This practically does nothing because i is already equal to mid. As a result, the search range is not moved at all!

The solution is by using a small trick: instead of calculating mid as mid = (i+j)/2, we now do:
mid = (i+j)/2+1  
Why does this trick work? When we use mid = (i+j)/2, the mid is rounded to the lowest integer. In other words, mid is always biased towards the left. This means we could have i == mid when j - i == mid, but we NEVER have j == mid. So in order to keep the search range moving, you must make sure the new i is set to something different than mid, otherwise we are at the risk that i gets stuck. But for the new j, it is okay if we set it to mid, since it was not equal to mid anyways. Our two rules in search of the left boundary happen to satisfy these requirements, so it works perfectly in that situation. Similarly, when we search for the right boundary, we must make sure i won't get stuck when we set the new i to i = mid. The easiest way to achieve this is by making mid biased to the right, i.e. mid = (i+j)/2+1.

2014年的文章, 也不知道是不是当时整个discussion还对binary search不熟悉还是怎么回事, 感觉这里的很多分析都太imperative了; 实际上按照我自己总结的经验, 直接一个闭区间二叉的就解决了;

当然, 如果不是提前在三分地看到了关于"二叉找区间"这样的论断, 我估计这题也没有办法这么快写出来答案; 这题实际上真正用的时间只有15分钟左右;

All this reasoning boils down to the following simple code:

    vector<int> searchRange(int A[], int n, int target) {  
        int i = 0, j = n - 1;  
        vector<int> ret(2, -1);  
        // Search for the left one  
        while (i < j)  
        {  
            int mid = (i + j) /2;  
            if (A[mid] < target) i = mid + 1;  
            else j = mid;  
        }  
        if (A[i]!=target) return ret;  
        else ret[0] = i;  

        // Search for the right one  
        j = n-1;  // We don't have to set i to 0 the second time.  
        while (i < j)  
        {  
            int mid = (i + j) /2 + 1; // Make mid biased to the right  
            if (A[mid] > target) j = mid - 1;    
            else i = mid;             // So that this won't make the search range stuck.  
        }  
        ret[1] = j;  
        return ret;   
    }

看他第一个循环返回出来的i, 是不需要判断bound的, 因为他这个不是我这种写法, 最后返回的不是insertion position, 也根本不会出界;

@cfjmonkey said in Clean iterative solution with two binary searches (with explanation):

int mid = (i + j + 1) /2;

for the second search may be a little better.

确实, 直接在外面+1给的biase好像太多了;

@stealflowercow said in Clean iterative solution with two binary searches (with explanation):

use the standard library you can do this like this :

   class Solution {  
            public:  
        vector<int> searchRange(vector<int>& nums, int target) {  

            auto lit=lower_bound(nums.begin(),nums.end(),target);  
            auto rit=upper_bound(nums.begin(),nums.end(),target);  
            --rit;  
            if(*lit!=target||(*rit)!=target)  
                return {-1,-1};  
            return {lit-nums.begin(),rit-nums.begin()};  
        }  
    };

本来以为这个是O(N), 不过好像实际上实现的是lgN的:

@stellari said in Clean iterative solution with two binary searches (with explanation):

I'd definitely go for this solution in a real-world application; it is concise, uses STL and runs in O(logN) time. However, it is likely that this solution is not acceptable as-is by the interviewer, since it does not show your ability (or lack thereof) to implement a binary search. He may ask you to implement your own lower_bound / upper_bound function instead.

另外, OP的一个小失误:

@scheung said in Clean iterative solution with two binary searches (with explanation):

I think your case 2 is incorrect:

"case 2: [5 3] (A[i] = target > A[j])"

This case cannot occur(3 cannot appear after 5) because the array is sorted. Please let me know if I have misunderstood.

突然反应过来这个OP就是那个连Stefan都很敬佩的大神, 啰嗦好像是这个人一贯的作风了;

@stellari said in Clean iterative solution with two binary searches (with explanation):

@lym5523 Of course the right-biased mid does NOT improve time efficiency. Why would you think it was used for that purpose? It is NOT "better" either. I chose to do that simply because given the way the logic is implemented, the mid HAS to be biased to the right or the loop will enter an infinite cycle. I prefer this implementation because the first and second half look mathematically symmetrical, not because it has an advantage in running time.

@kxcf said in A very simple Java solution, with only one binary search algorithm:

public class Solution {  
    public int[] searchRange(int[] A, int target) {  
        int start = Solution.firstGreaterEqual(A, target);  
        if (start == A.length || A[start] != target) {  
            return new int[]{-1, -1};  
        }  
        return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};  
    }  

    //find the first number that is greater than or equal to target.  
    //could return A.length if target is greater than A[A.length-1].  
    //actually this is the same as lower_bound in C++ STL.  
    private static int firstGreaterEqual(int[] A, int target) {  
        int low = 0, high = A.length;  
        while (low < high) {  
            int mid = low + ((high - low) >> 1);  
            //low <= mid < high  
            if (A[mid] < target) {  
                low = mid + 1;  
            } else {  
                //should not be mid-1 when A[mid]==target.  
                //could be mid even if A[mid]>target because mid<high.  
                high = mid;  
            }  
        }  
        return low;  
    }  
}

以前强调过, 虽然有些时候binary search的写法是开区间, 但是实际上你思考invariant的时候, 还是闭区间[lo, hi]. 也就是: the first larger_or_greater element is in range [lo, hi].

另外, 假如刚开始写二叉无法理解的时候, 可以直接尝试用三叉来分析, 然后看等号这一叉往哪边合并; 一般尤其是开区间写法, 都是可以合并的;

另外, 这里想到, 分析长度为2的区间的时候你的程序能跑的怎么样, 很能帮助避免出现no terminate的问题; 虽然我现在对于大部分的binary search算法有所总结所以不是很担心这个问题, 但是假如碰到了可能出现这个问题的题目, 至少要知道还有这一手.

另外, 这里一个小技巧, 就是找target + 1, 这个还是有点聪明的;

@leetcodeone said in A very simple Java solution, with only one binary search algorithm:

basically it is the same idea with using separate binary search for left and right bounds.
The good point here is the lower_bound and the search for (target+1)

这个人认为自己的代码是1pass:

@us917 said in Can solution be obtained in one pass:

My Python code is one pass, isn't it?

class Solution:  
# @param A, a list of integers  
# @param target, an integer to be searched  
# @return a list of length 2, [index1, index2]  
def searchRange(self, A, target):  
    if not A:  
        return [-1, -1]  
    return self.search(A, 0, len(A)-1, target)  

def search(self, A, start, end, target):  
    if A[start]>target or A[end]<target:  
        return [-1, -1]  
    if A[start] == target and A[end] == target:  
        return [start, end]  
    m = start+(end-start)/2  
    l = self.search(A, start, m, target)  
    r = self.search(A, m+1, end, target)  
    if l == [-1, -1] and r == [-1, -1]:  
        return [-1, -1]  
    if l == [-1, -1]:  
        return r  
    if r == [-1, -1]:  
        return l  
    return [l[0], r[1]]

但是Stefan他们好像都不认同;

@StefanPochmann said in Can solution be obtained in one pass:

I agree it's not one "pass", but "there is recursion" is insufficient reason. You could write ordinary binary search as recursion, and it would be one "pass". The full reason is that the two recursive calls can lead to two separate paths of length O(log n), which I consider two passes. Only two, though. This doesn't explode exponentially as one might think at first sight.

This is a quite neat algorithm and I took the liberty to rewrite and explain it and its runtime here.

说的是有道理的, 两个recursive call, 最后实际上是两条path;

Stefan后来还自己开了一个帖子专门讲这个代码;

@StefanPochmann said in 9-11 lines O(log n):

Solution 1 : Divide and Conquer with early breaks : 56 ms

The O(log n) time isn't quite obvious, so I'll explain it below. Or you can take the challenge and prove it yourself :-)
def searchRange(self, nums, target):  
    def search(lo, hi):  
        if nums[lo] == target == nums[hi]:  
            return [lo, hi]  
        if nums[lo] <= target <= nums[hi]:  
            mid = (lo + hi) / 2  
            l, r = search(lo, mid), search(mid+1, hi)  
            return max(l, r) if -1 in l+r else [l[0], r[1]]  
        return [-1, -1]  
    return search(0, len(nums)-1)  
The search helper function returns an index range just like the requested searchRange function, but only searches in nums[lo..hi]. It first compares the end points and immediately returns [lo, hi] if that whole part of nums is full of target, and immediately returns [-1, -1] if target is outside the range. The interesting case is when target can be in the range but doesn't fill it completely.

In that case, we split the range in left and right half, solve them recursively, and combine their results appropriately. Why doesn't this explode exponentially? Well, let's call the numbers in the left half A, ..., B and the numbers in the right half C, ..., D. Now if one of them immediately return their [lo, hi] or [-1, -1], then this doesn't explode. And if neither immediately returns, that means we have A <= target <= B and C <= target <= D. And since nums is sorted, we actually have target <= B <= C <= target, so B = C = target. The left half thus ends with target and the right half starts with it. I highlight that because it's important. Now consider what happens further. The left half gets halved again. Call the middle elements a and b, so the left half is A, ..., a, b, ..., B. Then a <= target and:

If a < target, then the call analyzing A, ..., a immediately returns [-1, -1] and we only look further into b, ..., B which is again a part that ends with target.

If a == target, then a = b = ... = B = target and thus the call analyzing b, ..., B immediately returns its [lo, hi] and we only look further into A, ..., a which is again a part that ends with target.

Same for the right half C, ..., D. So in the beginning of the search, as long as target is only in at most one of the two halves (so the other immediately stops), we have a single path. And if we ever come across the case where target is in both halves, then we split into two paths, but then each of those remains a single path. And both paths are only O(log n) long, so we have overall runtime O(log n).

This is btw based on us917's solution.

跑一个trace看看(打草稿的时候横向可能更方便): 5,7,7,8,8,10 and 8. 注意缩进只用来表达recursion level, 而不是跟你写代码那样, 用来表示当前iteration的代码的从属关系; 一个iteration就给一行就可以了, 从左到右代表flow的顺序;

(0, 5): mid = 2, (l, r) = ([-1, -1], [3, 5]), return [3, 4]  
    (0, 2): mid = 1, return [-1, -1]  
    (3, 5): mid = 4, (l, r) = ([3, 4], [5, 5]), return [3, 4]  
        (3, 4): mid = 3, (l, r) = ([3,3], [4,4]), return [3, 4]  
            (3, 3): return [3, 3]  
            (4, 4): return [4, 4]  
        (5, 5): return [-1, -1]

可以看到, trace一个recursion其实也并不困难, 无论是手写还是打字;

trace完了大概就理解这个算法的设计思路了, 严格来说, 这个不能算是一个Binary Search的思路, 叫做divide&conquer反而更加贴切(虽然两者的定义并不是完全的互相独立). 一个关键点就是你看他分区间的方式: [0, mid] and [mid + 1, hi]. 每一个位置都是保证被cover的;

divide&conquer和开区间二叉

也许divide&conquer就是开区间二叉写法背后的intuition? 以前真的没有从这个角度来理解过? 不过这么想实际上还是合理的; 用recursion的input角度来理解, 好像直观很多;

注意看他nums[lo] <= target <= nums[hi]的写法: 很明显这里的invariant判断的就是闭区间了(again, 虽然写法是开区间, 不对, 写法其实也是闭区间, 这里在分区间的时候的类似hi = mid的操作是因为divide&conquer的关系).

另外, Stefan这里这个时间分析可以说是非常到位了, 我没想到这个做法居然还真的可以在很多情况下做到1pass. 相比于我们之前的普通的iterative的做法, 这个recursive的做法更加智能, do two passes only when necessary.

另外, 关于最后那个Python语法的使用:

@StefanPochmann said in 9-11 lines O(log n):

l and r are the results for the left and right half, so that just tests whether one of them is doesn't contain the target (e.g., if l+r is [3, 5, -1, -1]).

Solution 2 : Two binary searches : 56 ms

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

Here, my helper function is a simple binary search, telling me the first index where I could insert a number n into nums to keep it sorted. Thus, if nums contains target, I can find the first occurrence with search(target). I do that, and if target isn't actually there, then I return [-1, -1]. Otherwise, I ask search(target+1), which tells me the first index where I could insert target+1, which of course is one index behind the last index containing target, so all I have left to do is subtract 1.

跟上面那个借用STL的算法是类似的, 不过那个算法是2014年发的, 这个是2015年;

Solution 3 : Two binary searches, using the library

Binary search is so good and common that many languages have it in their standard library and you just need to figure out how to apply it to the problem at hand.

Python:

def searchRange(self, nums, target):  
    lo = bisect.bisect_left(nums, target)  
    return [lo, bisect.bisect(nums, target)-1] if target in nums[lo:lo+1] else [-1, -1]

C++:

vector<int> searchRange(vector<int>& nums, int target) {  
    auto bounds = equal_range(nums.begin(), nums.end(), target);  
    if (bounds.first == bounds.second)  
        return {-1, -1};  
    return {bounds.first - nums.begin(), bounds.second - nums.begin() - 1};  
}

Or:

vector<int> searchRange(vector<int>& nums, int target) {  
    int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();  
    if (lo == nums.size() || nums[lo] != target)  
        return {-1, -1};  
    int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;  
    return {lo, hi};  
}

Java:

Well, Java decided to be annoying and offer Arrays.binSearch but with "If the array contains multiple elements with the specified value, there is no guarantee which one will be found". So it's useless for us. I'm not good at Java, though, so maybe I'm overlooking a way to still make it work. If you manage to do so, please let me know.

@jianchao.li.fighter said in 9-11 lines O(log n):

I really like the first Divide and Conquer solution and the proof of its running time. I rewrite it in C++ and it achieves the fastest running time (12 ms) among the C++ codes :-)

class Solution {  
public:  
    vector<int> searchRange(vector<int>& nums, int target) {  
        int n = nums.size();  
        return search(nums, 0, n - 1, target);  
    }  
private:   
    vector<int> search(vector<int>& nums, int l, int r, int target) {  
        if (nums[l] == target && nums[r] == target) return {l, r};  
        if (nums[l] <= target && target <= nums[r]) {  
            int mid = l + ((r - l) >> 1);  
            vector<int> left = search(nums, l, mid, target);  
            vector<int> right = search(nums, mid  +1, r, target);  
            if (left[0] == -1) return right;  
            if (right[0] == -1) return left;  
            return {left[0], right[1]};  
        }  
        return {-1, -1};  
    }  
};

BTW, thanks to the great C++ 11 features of vector initialization using {}, which saves a lot of codes :-)

Update: an absolutely high-quality post. I read through all the solutions and learn a lot from them, the algorithm, the proof, and the details of the codes. Thanks a lot!

他也意识到了是divide&conquer;

@xuanaux said in Simple and strict O(logn) solution in Java using recursion:

public class Solution {  
    public int[] searchRange(int[] A, int target) {  
        int[] range = {A.length, -1};  
        searchRange(A, target, 0, A.length - 1, range);  
        if (range[0] > range[1]) range[0] = -1;   
        return range;  
    }  

    public void searchRange(int[] A, int target, int left, int right, int[] range) {  
        if (left > right) return;  
        int mid = left + (right - left) / 2;  
        if (A[mid] == target) {  
            if (mid < range[0]) {  
                range[0] = mid;  
                searchRange(A, target, left, mid - 1, range);  
            }  
            if (mid > range[1]) {  
                range[1] = mid;  
                searchRange(A, target, mid + 1, right, range);  
            }  
        } else if (A[mid] < target) {  
            searchRange(A, target, mid + 1, right, range);  
        } else {  
            searchRange(A, target, left, mid - 1, range);  
        }  
    }  
}

看起来跟我的思路非常的类似, 实际上还是有区别的, 首先recursion在这个题目上面有自然的优势, 这个前面已经说过了, 另外, 他这里对于==情况的处理: 他用一个accum来收集所有的hit位置的范围(min index and max index). 因为是sorted, 所以这样两个end就可以代表整个range; 整个代码declarative解释起来比我的方便很多;

submission最优解, 其实只是波动:

class Solution {  
    public int[] searchRange(int[] nums, int target) { //二分法  
        int[] result = new int[2];  
        result[0] = firsttarget(nums, target);  
        result[1] = lasttarget(nums, target);  
        return result;  
    }  
    public int firsttarget(int[] nums, int target) {  
        int lo = 0;  
        int hi = nums.length - 1;  
        int idx = -1;  
        while (lo <= hi) {  
            int mid = (lo + hi) / 2;  

            if (target <= nums[mid]) {  
                hi = mid - 1;  
            }  
            else {  
                lo = mid + 1;  
            }  
            if (nums[mid] == target) {  
                idx = mid;  
            }  
        }  

        return idx;  
    }  

    public int lasttarget(int[] nums, int target) {  
        int lo = 0;  
        int hi = nums.length - 1;  
        int idx = -1;  
        while (lo <= hi) {  
            int mid = (lo + hi) / 2;  
            if (target < nums[mid]) {  
                hi = mid - 1;  
            }  
            else {  
                lo = mid + 1;  
            }  
            if (nums[mid] == target) {  
                idx = mid;  
            }  
        }  

        return idx;  
    }  
}

这个算法跟上面之前看到的那个算法是类似的, 直接就是找到第一个和最后一个occurrence. binary search本身的写法上面稍微有点变化来控制在==情况下的走的位置, 这样当你hit到target的run当中的时候, 会往正确的方向移动;

Problem Description

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Difficulty:Medium
Total Accepted:174.2K
Total Submissions:551.5K
Contributor:LeetCode
Companies
linkedin
Related Topics
arraybinary search
Similar Questions
First Bad Version

LC34 SearchForARange

SearchForARange [source code]

editorial

Approach #1 Linear Scan [Accepted]

Approach #2 Binary Search [Accepted]

divide&conquer和开区间二叉

Problem Description

results matching ""

No results matching ""