首页 > 其他 > 详细

34. Search for a Range

时间:2017-10-22 20:48:33      阅读:292      评论:0      收藏:0      [点我收藏+]
34. Search for a Range

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,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} target
 4  * @return {number[]}
 5  */
 6 var searchRange = function(nums, target) {
 7     
 8     var len = nums.length;
 9     var start = -1,end =start;
10     
11     var i = 0;
12     var j = len -1;
13     
14     
15     
16     while(i <= j){
17         
18         var mid = Math.floor((i+j)/2);
19         
20         if(target === nums[mid]){
21            start = end = mid;
22             break;
23         }
24         
25         if(target < nums[mid]){
26             
27             j = mid -1;
28         }else{
29             
30             i = mid + 1;
31         }       
32                 
33     }
34     
35     
36     while(start - 1 >= 0 && nums[start - 1] == target){
37             
38             start -= 1;
39             
40      }
41         
42     while(end + 1 <= len -1 && nums[end + 1] == target){
43             end += 1; 
44     }
45     
46     
47     var res = [];
48     
49     res.push(start);
50     res.push(end);
51     
52     return res;
53 };

 

34. Search for a Range

原文:http://www.cnblogs.com/huenchao/p/7710503.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!