Leetcode 34 - Search for a Range

Given a sorted array of integers, 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].


X.
https://discuss.leetcode.com/topic/6327/a-very-simple-java-solution-with-only-one-binary-search-algorithm

 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;
 }

https://discuss.leetcode.com/topic/16486/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, ..., Bwhich 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.

---

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.

---

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);
    return *bounds.first != target ? vector<int> {-1, -1} :
                                     vector<int> {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 (nums[lo] != target)
        return vector<int> {-1, -1};
    int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
    return vector<int> {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.

X. With only one binary search algorithm - not efficient

http://www.programcreek.com/2014/04/leetcode-search-for-a-range-java/

public int[] searchRange(int[] nums, int target) {
    if(nums == null || nums.length == 0){
        return null;
    }
 
    int[] arr= new int[2];
    arr[0]=-1;
    arr[1]=-1;
 
    binarySearch(nums, 0, nums.length-1, target, arr);
    return arr;
}
 
public void binarySearch(int[] nums, int left, int right, int target, int[] arr){
    if(right<left) 
        return;
 
    if(nums[left]==nums[right] && nums[left]==target){
        arr[0]=left;
        arr[1]=right;
        return;
    }
 
    int mid = left+(right-left)/2;
 
 
    if(nums[mid]<target){
        binarySearch(nums, mid+1, right, target, arr);
    }else if(nums[mid]>target){
        binarySearch(nums, left, mid-1, target, arr);
    }else{
        arr[0]=mid;
        arr[1]=mid;
 
        //handle duplicates - left
        int t1 = mid;
        while(t1 >left && nums[t1]==nums[t1-1]){
            t1--;
            arr[0]=t1;
        }
 
        //handle duplicates - right
        int t2 = mid;
        while(t2 < right&& nums[t2]==nums[t2+1]){
            t2++;
            arr[1]=t2;
        }
        return;
    }

https://leetcode.com/discuss/29228/simple-and-strict-o-logn-solution-in-java-using-recursion
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); } }
X.
https://leetcode.com/discuss/18242/clean-iterative-solution-binary-searches-with-explanation
https://leetcode.com/discuss/52701/easy-java-o-logn-solution
public int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = findFirst(nums, target); result[1] = findLast(nums, target); return result; } private int findFirst(int[] nums, int target){ int idx = -1; int start = 0; int end = nums.length - 1; while(start <= end){ int mid = (start + end) / 2; if(nums[mid] >= target){ end = mid - 1; }else{ start = mid + 1; } if(nums[mid] == target) idx = mid; } return idx; } private int findLast(int[] nums, int target){ int idx = -1; int start = 0; int end = nums.length - 1; while(start <= end){ int mid = (start + end) / 2; if(nums[mid] <= target){ start = mid + 1; }else{ end = mid - 1; } if(nums[mid] == target) idx = mid; } return idx; }
如果我们不寻找那个元素先，而是直接相等的时候也向一个方向继续夹逼，如果向右夹逼，最后就会停在右边界，而向左夹逼则会停在左边界，如此用停下来的两个边界就可以知道结果了，只需要两次二分查找
http://www.jiuzhang.com/solutions/search-for-a-range/

    public int[] searchRange(int[] A, int target) {
        if (A.length == 0) {
            return new int[]{-1, -1};
        }
        
        int start, end, mid;
        int[] bound = new int[2]; 
        
        // search for left bound
        start = 0; 
        end = A.length - 1;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[start] == target) {
            bound[0] = start;
        } else if (A[end] == target) {
            bound[0] = end;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }
        
        // search for right bound
        start = 0;
        end = A.length - 1;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                start = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] == target) {
            bound[1] = end;
        } else if (A[start] == target) {
            bound[1] = start;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }
        
        return bound;
    }

http://www.lifeincode.net/programming/leetcode-search-for-a-range-java/

    public int[] searchRange(int[] A, int target) {

        int[] ret = {-1, -1};

        int start = 0;

        int end = A.length - 1;

        while (start < end) {

            int mid = (start + end) / 2;

            if (A[mid] < target)

                start = mid + 1;

            else

                end = mid;

        }

        int low;

        if (A[start] != target)

            return ret;

        else

            low = start;

        start = 0;

        end = A.length - 1;

        while (start < end) {

            int mid = (start + end) / 2;

            if (A[mid] < target + 1)

                start = mid + 1;

            else

                end = mid;

        }

        int high = A[start] == target ? start : start - 1;

        ret[0] = low;

        ret[1] = high;

        return ret;

    }

https://leetcode.com/discuss/19368/very-simple-java-solution-with-only-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)

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; }
X. http://www.cnblogs.com/springfor/p/3857704.html

第一步，在给定数组中找到该target，记录该位置。这时我们并不关心这个target是边界还是中间值，我们只需确定，在数组中是能够找到这样一个target值。如果找不到返回{-1，-1}。为了保证时间复杂度是O(logn), 这里自然而然使用传统二分查找法实现。

第二步，确定该target的右边界。此时我们将对数组从刚才确定的那个target的pos作为起始点，到数组结束，来确定右边界。同样是使用二分查找法，当新的mid值仍然等于target值时，我们能确定该mid左半边（到pos）都是等于target，继续在右半边查找。如果新的mid值不等于target值，我们就知道右边界一定在新mid值的左半边，继续查找。最后新的high指针指向的就是右边界的位置。

第三步，确定该target的左边界。这一步与第二步对称操作，最后新的low指针指向的就是左边界的位置。

 1     public int[] searchRange(int[] A, int target) {
 2         int [] res = {-1,-1};
 3         if(A == null || A.length == 0)
 4             return res;
 5         
 6         //first iteration, find target wherever it is
 7         int low = 0;
 8         int high = A.length-1;
 9         int pos = 0;
10         while(low <= high){
11             int mid = (low + high)/2;
12             pos = mid;
13             if(A[mid] > target)
14                 high = mid - 1;
15             else if(A[mid] < target)
16                 low = mid + 1;
17             else{
18                 res[0] = pos;
19                 res[1] = pos;
20                 break;
21             }
22         }
23         
24         if(A[pos] != target)
25             return res;
26         
27         //second iteration, find the right boundary of this target
28         int newlow = pos;
29         int newhigh = A.length-1;
30         while(newlow <= newhigh){
31             int newmid = (newlow+newhigh)/2;
32             if(A[newmid] == target)
33                 newlow = newmid + 1;
34             else
35                 newhigh = newmid - 1;
36         }
37         res[1] = newhigh;
38         
39         //third iteration, find the left boundary of this target
40         newlow = 0;
41         newhigh = pos;
42         while(newlow <= newhigh){
43             int newmid = (newlow+newhigh)/2;
44             if(A[newmid] == target)
45                 newhigh = newmid - 1;
46             else
47                 newlow = newmid + 1;
48         }
49         res[0] = newlow;
50         
51         return res;
52     }

http://www.darrensunny.me/leetcode-search-for-a-range/

public int[] searchRange(int[] A, int target) {

    int[] result = {-1, -1};

    int n = A.length;

    if (A == null || n == 0)

        return result;

    // Find one target first

    int separator = -1;         // The index of one of several appearances of target

    int left = 0, right = n-1;

    while (left <= right) {

        int middle = (left+right) / 2;

        if (A[middle] > target) {   // target must be at the left half

            right = middle - 1;

        } else if (A[middle] < target) {    // target must be at the right half

            left = middle + 1;

        } else {            // Find one target

            separator = middle;

            break;

        }

    }

    if (separator == -1)        // No target exists

        return result;

    // Find the starting index within A[0...separator]

    left = 0;

    right = separator;

    while (left <= right) {

        int middle = (left+right) / 2;

        if (A[middle] == target)    // right will end up at right before the starting index

            right = middle - 1;

        else        // A[middle]<target; the starting index should be within [middle+1,right]

            left = middle + 1;

    }   // out of loop; left = right - 1, i.e. the starting index

    result[0] = left;   // Save the starting index in result[0]

    // Find the ending index within A[separator+1...n-1]

    left = separator;

    right = n - 1;

    while (left <= right) {

        int middle = (left+right) / 2;

        if (A[middle] == target)    // left will end up at right after the ending index

            left = middle + 1;

        else        // A[middle]>target; the starting index should be within [left, middle-1]

            right = middle - 1;

    }   // out of loop; right = left + 1, i.e. the ending index

    result[1] = right;  // Save the ending index in result[1]

    return result;

}

Also check http://zhaohongze.com/wordpress/2014/01/05/leetcode-search-for-a-range/
Read full article from 西小瓜: Leetcode: Search for a Range