首页 > 代码库 > 搜索区间

搜索区间

2024-09-19 07:10:26   222人阅读

http://www.lintcode.com/zh-cn/problem/search-for-a-range/

错误点： 1。返回值类型int[]，所以return new int[] {-1, -1}， 而不要写 new {-1, -1}，后者不精确

　　　　 2。在给结果赋值时，考虑到有 [1,1,1,1,1,1]  1 的情况，所以考虑好if语句赋值的先后顺序。

注意点：  结果返回时， int[] result = new int[2] ，赋值时给result[0] 、[1]赋值即可，不用每次都new新数组返回。

技术分享 
 1  public int[] searchRange(int[] A, int target) {
 2         // write your code here
 3         //if (A == null || A.length == 0) {
 4         if (A.length == 0) {
 5             return new int[] {-1, -1};
 6         }
 7         int[] bound = new int[2];
 8         //左边界确定
 9         int start, end, mid;
10         start = 0; end = A.length - 1;
11         while(end - start > 1) {
12             mid = start + (end - start) / 2;
13             if (A[mid] >= target) {
14                 end = mid; 
15             } else {
16                 start = mid;
17             }
18         }
19         if (A[start] == target) {
20             bound[0] = start;
21         } else if (A[end] == target) {
22             bound[0] = end;
23         } else {
24             bound[0] = bound[1] = -1;
25             return bound;
26         }
27         //右边界确定
28         start = 0; end = A.length - 1;
29         while(end - start > 1) {
30             mid = start + (end - start) / 2;
31             if (A[mid] <= target) {
32                 start = mid; 
33             } else {
34                 end = mid;
35             }
36         }
37         if (A[end] == target) {
38             bound[1] = end;
39         } else if (A[start] == target) {
40             bound[1] = start;
41         } else {
42             bound[0] = bound[1] = -1;
43             return bound;
44         }
45         return bound;
46     }
View Code

 

搜索区间


联系
我们