[leetcode]Search for a Range

Hello everyone , I meet you again , I'm the king of the whole stack

A narrative statement of the problem ：

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

The basic idea ：

This problem can be solved by binary search .

Suppose there is no target, In the O（lgn） Time is over .

Let's say there's... In the array target, If I found target after , Continue to dichotomy the content before and after Find this location pos .

1. Ahead pos Need to meet A[pos] < target && A[pos+1] == target. pos+1 That is the starting position .
2. hinder pos Need to meet A[pos] > target && A[pos-1] == target . pos-1 It's the end position .

Code ：

vector<int> searchRange(int A[], int n, int target) {   //C++
        vector<int> result(2);
        
        int low = 0, high = n-1;
        int mid, begin = -1, end = -1;
        while(low <= high)
        {
            mid = (low+high)/2;
            if(A[mid] > target)
                high = mid - 1;
            else if(A[mid] < target)
                low = mid + 1;
            else 
            {
                    begin = mid;
                    end = mid;
                    
                    //get begin
                    if(low <= begin -1){
                        while((low <= begin-1) && !(A[low]<target && A[low+1] == target) )
                        {
                            mid = (low + begin-1)/2;
                            if(A[mid] < target)
                                low = mid+1;
                            else begin = mid;
                        }
                        if(A[low]<target && A[low+1] == target)
                            begin = low+1;
                    }
                    //get end
                    if(high >= end+1){
                        while((high >= end+1) &&!(A[high]>target && A[high-1] == target))
                        {
                            mid = (high + end +1)/2;
                            if(A[mid] > target)
                                high = mid - 1;
                            else end = mid;
                        }
                        if(A[high]>target && A[high-1] == target)
                            end = high - 1;
                    }
                    break;
                    
            }
        }
        result[0] = begin;
        result[1] = end;
        return result;
    }

Copy

Copyright notice ： This article is the original article of the blogger , Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116862.html Link to the original text ：https://javaforall.cn