Search for a Range

URL: 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].

var searchRange = function(nums, target) {
    var arr = [],
        temp;
    for(var i = 0,len = nums.length;i < len; i++){
        temp = nums[i];
        if(temp === target){
            arr.push(i);
        }
    }
    if(arr.length === 0){
        arr.push(-1);
        arr.push(-1);
    }else if(arr.length === 1){
        arr[arr.length] = arr[0];
    }else if(arr.length > 2){
        arr.splice(1,arr.length -2);
    }
    return arr;
};

感觉自己英文不够好,唉,时间复杂度也不对,先这么做,下次再做O(log n)。就是判断的时候,如果只出现一次的话,数组两个数字都是同一个位置。其他还好。

想了下,应该有个二分法,同时找最左边和最右边的,数组反正是 排过序的。下次写······

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据