卖萌的弱渣

I am stupid, I am hungry.

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].

Example

Given [5, 7, 7, 8, 8, 10] and target value 8,

return [3, 4].

Solution

  • Java: 两次二分
(Search-for-A-Range.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[] ret = {-1, -1};
        if(n==0) return ret;
        int l = 0;
        int r = n-1;

        while(l<=r){
            int mid = l+(r-l)/2;
            if(nums[mid]<target)
                l = mid+1;
            else
                r = mid-1;
        }
        // 有可能找不到
        if(l>=n || nums[l]!=target) return ret;
        ret[0] = l;

        l=0;
        r = n-1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(nums[mid]<=target)
                l = mid+1;
            else
                r = mid-1;
        }
        ret[1] = r;
        return ret;
    }
}
  • Python: Binary Search
(Search-for-a-Range.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1,-1]
        ret = [-1,-1]
        start = 0
        end = len(nums)-1

        while start <= end:
            mid = (start+end)/2
            if target == nums[mid]:
                break
            elif target > nums[mid]:
                start = mid+1
            else:
                end = mid-1
        # Not found
        if start > end:
            return ret

        l = mid
        r = mid
  # Find range       
  while l>0 and  nums[mid] == nums[l-1]:
            l -= 1
        while r < end and nums[mid] == nums[r+1]:
            r += 1
        return [l,r]