Search for a Range, Leetcode 解题笔记

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

题目要求复杂度是O(log n),肯定是用binary search。如果直接二分查找target然后再向左右两边找端点,最差复杂度是O(n)。所以应该做两次binary search分别查找左端点和右端点。与标准binary search不同的是,当我们遇到A[mid] = target时,并不返回mid,而是继续让right=mid,这样到最后找到的是左端点。然后再来一遍找到target+1的左端点(即target的右端点)。
实现时注意两种特殊情况:
1.array里全是target。
2.array里没有target。

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] ret = {-1, -1};
        int left = 0;
        int right = A.length-1;
        
        while(left < right){
            int mid = (left + right)/2;
            if(A[mid] < target){
                left = mid+1;
            }
            else{
                right = mid;
            }
        }
        
        if(A[left] != target) return ret;
        ret[0] = left;
        
        left = 0;
        right = A.length-1;
        while(left < right){
            int mid = (left + right)/2;
            if(A[mid] < target+1){
                left = mid+1;
            }
            else{
                right = mid;
            }
        }
        if(A[left] != target)
            ret[1] = left-1;
        else
            ret[1] = left;
        return ret;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s