leetcode第33题--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].

给的那个一个有序数组和一个目标target，找到这个目标在有序数组里的开始和结束的下标。如果不存在就返回 -1 -1。注，如果数组中目标值只有一个，那就返回两个相同的下标。

用binary search找到target 然后再在左边binary search找到左边（包括mid）第一个目标，记录下标。再在右边binary 找到最后一个目标。记录下标。返回。

代码如下：

class Solution {

public:

vector<int> searchRange(int A[], int n, int target)

{

    vector<int> wr, ans;

    wr.push_back(-1); // 要学会可以用 vector<int> wr(2,-1);直接将其初始化为想要的

    wr.push_back(-1);

    if(n == 0)

    return wr;

    int l = 0, r = n -1, mid = 0;

    while(l <= r)

    {

        mid = (l+r)/2;

        if (A[mid] < target) // 如果mid小于target那么可以把左边一块去掉

        {

            l = mid + 1;

            continue;

        }

        if (A[mid] > target) // 如果mid大于target那么可以把右边一块去掉

        {

            r = mid -1;

            continue;

        }

        if (A[mid] == target)// mid 找到了刚好，那就肯定在这里面要有return，如果一直没有找到，跳出while后就返回wr

        {

            // find start from l to mid，binary search

            int start = l, l_r = mid; // l_r指mid左边的最右

            while(l <= l_r)

            {

                int tmp_mid = (l + l_r)/2;

                if(A[tmp_mid] != target)

                    {l = tmp_mid + 1;}

                if(A[tmp_mid] == target)

                    {l_r = tmp_mid - 1; start = tmp_mid;}

            }

            ans.push_back(start);

            // find end from mid to r，binary search

            int r_l = mid, End = mid; // r_l指mid右边的最左

            while(r_l <= r)

            {

                int tmp_mid = (r_l + r)/2;

                if(A[tmp_mid] != target)

                    {r = tmp_mid - 1;}

                if(A[tmp_mid] == target)

                    {r_l = tmp_mid + 1; End = tmp_mid;}

            }

            ans.push_back(End);

            return ans;

        }

    }

    return wr;

}

};

巴特西

leetcode第33题--Search for a Range

最新文章

热门文章