本文共 1341 字，大约阅读时间需要 4 分钟。

题目

Given an array of integers sorted in ascending order, 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,

分析

给出了一个int类型的升序的数组，查找数组中等于给出的数字的起始坐标和最终坐标。如果找不到和给出的数相等的数，就返回[-1, -1]。

因为数组已经排好序了，因此我们无须对该数组进行排序。

最简单的做法就是按顺序遍历整个数组，知道找到目标数，但是这个算法的时间复杂度为O(n)，明显大于题目所要求的O(log n)。

所以我们采用二分查找的算法求解改题目，而二分查找的时间复杂度为O(log n)，符合要求。

class Solution {public:    vector
   
     searchRange(vector
    
     & nums, int target) {        // 若数组为空，则不存在符合要求的数        if (nums.size() == 0) {            return {-1, -1};        }        int a = 0, b = nums.size() - 1;        int index = (b + a) / 2;        while (b >= a) {            if (nums[index] == target) {                int i, j;                for (i = index; nums[i] == target && i < nums.size(); i++);                for (j = index; nums[j] == target && j >= 0; j--);                return {j+1, i-1};            } else if (nums[index] >target) {                b = index - 1;                index = (b + a) / 2;            } else {                a = index + 1;                index = (b + a) / 2;            }        }        return {-1, -1};    }};
    
   

转载地址：http://tibmb.baihongyu.com/