Tag:Lintcode 数组 二分法 C++
Category:Lintcode
Article From:https://www.cnblogs.com/Tang-tangt/p/9122471.html

Original website: https://www.lintcode.com/problem/search-for-a-range/description

Given a given onen Order an array of integers to find a given target valuetarget The starting and ending positions.

If the target value is not in the array, then returns[-1, -1]

Have you ever met this question in a real interview? Such

Sample

Give[5, 7, 7, 8, 8, 10]And target value target=8,

Return[3, 4]

Challenge

Time complexity O (log)n)

Label
dichotomy
array
Sort array
 
Train of thought: two points search. After finding, use two pointers to move forward separately, find the starting position, move backward and find the end position. Pay attention to the boundary elements.
The initial code does not take into account the empty set or the situation that is not found. We must consider the problem comprehensively, not because we have done similar questions.
start、endThe initial value is set to -2 to determine if target is found in the array, and the initial value is not -1 because if the initial location is 0 start will become -1, but end does not, so if the judgment is start==-1& & end==-1The initial value can also be -1…
 
ACCode:
class Solution {
public:
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    vector<int> searchRange(vector<int> &A, int target) {
        // write your code here
        int size=A.size();
    int left=0,right=size-1,middle=(left+right)/2;
    int start=-2,end=-2;
    vector<int> result(2,-1);
    //Two points lookup;
    while(left<=right)
    {
        if (A[middle]==target)
        {
            start=middle;
            end=middle;
            while(start>=0&&A[start]==target)
            {
                start--;
            }
            while(end<=size-1&&A[end]==target)
            {
                end++;
            }
            break;
        }
        else if (A[middle]<target)
        {
            left=middle+1;
            middle=(left+right)/2;
        }
        else
        {
            right=middle-1;
            middle=(left+right)/2;
        }
    }
    if (start==-2&&end==-2)//Can't find;
    {
        return result;
    }
    start+=1;
    end-=1;
    result[0]=start;
    result[1]=end;
    return result;
    }
};

You can also use library functions, lower_bound and upper_bound, for reference: https://blog.csdn.net/wangyuquanliuli/article/details/46642637

C++Medium lower_bound function and upper_bound function

 

Link of this Article: 61 search interval

Leave a Reply

Your email address will not be published. Required fields are marked *