题目

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(logn)内。

明显的，我们应该采取二分搜索的思想，设计求出关键字最早出现位置与最后出现位置，与普通的二叉搜索比较，只需要修改判断条件即可。

AC代码

class Solution {

public:

    vector<int> searchRange(vector<int>& nums, int target) {

        vector<int> ret;

        if (nums.size() == 0)

        {

            ret.push_back(-1);

            ret.push_back(-1);

            return ret;

        }

        //寻找目标元素的下标

        int pos = BinarySearch(nums, target);

        //目标元素不存在

        if (pos == -1)

        {

            ret.push_back(-1);

            ret.push_back(-1);

            return ret;

        }

        else{

            int left = BinarySearchLeft(nums, 0, pos, target);

            int right = BinarySearchRight(nums, pos, nums.size()-1 , target);

            ret.push_back(left);

            ret.push_back(right);

            return ret;

        }//if

    }

    int BinarySearch(vector<int> & nums, int target)

    {

        int left = 0, right = nums.size() - 1;

        while (left <= right)

        {

            int mid = (left + right) / 2;

            if (nums[mid] == target)

                return mid;

            else if (nums[mid] < target)

            {

                left = mid + 1;

                continue;

            }

            else{

                right = mid - 1;

                continue;

            }

        }//while

        return -1;

    }

    int BinarySearchLeft(vector<int> & nums, int left, int right, int target)

    {

        while (left < right)

        {

            int mid = (left + right) / 2;

            if (nums[mid] == target && nums[mid-1] < target)

                return mid;

            else if (nums[mid] < target)

            {

                left = mid + 1;

                continue;

            }

            else{

                right = mid - 1;

                continue;

            }

        }//while

        return left;

    }

    int BinarySearchRight(vector<int> & nums, int left, int right, int target)

    {

        while (left < right)

        {

            int mid = (left + right) / 2;

            if (nums[mid] == target && nums[mid + 1] > target)

                return mid;

            else if (nums[mid] <= target)

            {

                left = mid + 1;

                continue;

            }

            else{

                right = mid - 1;

                continue;

            }

        }//while

        return right;

    }

};

GitHub测试程序源码