leetcode -- Search for a Range
添加时间:2013-8-1 点击量:
Given a sorted array of integers， find the starting and ending position of a given target value.
Your algorithms 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的idx，然后查看该idx的阁下断定局限。
算法错杂度：
均匀景象下是O（lgn）;
最坏景象下数组中所有元素都雷同O（n）;
1 public class Solution {
2 public int[] searchRange（int[] A， int target） {
3 // Start typing your Java solution below
4 // DO NOT write main（） function
5 int idx = binarySearch（A， target）;
6 int len = A.length;
7 int[] results = null;
8 if（idx == -1）{
9 results = new int[]{-1， -1};
10 } else{
11 int l = idx;
12 int r = idx;
13 while（l >= 0 && A[l] == target）{
14 l--;
15 }
16 l++;
17
18 while（r < len && A[r] == target）{
19 r++;
20 }
21 r--;
22 results = new int[]{l， r};
23 }
24 return results;
25 }
26
27 public int binarySearch（int[] A， int target）{
28 int len = A.length;
29 int l = 0， r = len - 1;
30 while（l <= r）{
31 int mid = （l + r） / 2;
32 if（target == A[mid]）
33 return mid;
34
35 if（target > A[mid]）{
36 l = mid + 1;
37 } else {
38 r = mid - 1;
39 }
40 }
41
42 return -1;
43 }
44 }
所有随风而逝的都属于昨天的，所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
Given a sorted array of integers， find the starting and ending position of a given target value.
Your algorithms 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的idx，然后查看该idx的阁下断定局限。
算法错杂度：
均匀景象下是O（lgn）;
最坏景象下数组中所有元素都雷同O（n）;
1 public class Solution {
2 public int[] searchRange（int[] A， int target） {
3 // Start typing your Java solution below
4 // DO NOT write main（） function
5 int idx = binarySearch（A， target）;
6 int len = A.length;
7 int[] results = null;
8 if（idx == -1）{
9 results = new int[]{-1， -1};
10 } else{
11 int l = idx;
12 int r = idx;
13 while（l >= 0 && A[l] == target）{
14 l--;
15 }
16 l++;
17
18 while（r < len && A[r] == target）{
19 r++;
20 }
21 r--;
22 results = new int[]{l， r};
23 }
24 return results;
25 }
26
27 public int binarySearch（int[] A， int target）{
28 int len = A.length;
29 int l = 0， r = len - 1;
30 while（l <= r）{
31 int mid = （l + r） / 2;
32 if（target == A[mid]）
33 return mid;
34
35 if（target > A[mid]）{
36 l = mid + 1;
37 } else {
38 r = mid - 1;
39 }
40 }
41
42 return -1;
43 }
44 }
所有随风而逝的都属于昨天的，所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
