(34)Search for a Range

 1 public class SearchForRange {
 2     public static int[] searchRange(int[] A, int target) {
 3         // search for left bound
 4         int start, end, mid;
 5         start = 0;
 6         end = A.length - 1;
 7         int[] bound = new int[2];
 8         while (start + 1 < end) {
 9             mid = start + (end - start) / 2;
10             if (A[mid] == target)
11                 end = mid;
12             else if (A[mid] < target)
13                 start = mid;
14             else
15                 end = mid;
16         }
17 
18         if (A[start] == target)
19             bound[0] = start;
20         else if (A[end] == target)
21             bound[0] = end;
22         else {
23             bound[0] = bound[1] = -1;
24             return bound;
25         }
26 
27         System.out.println("left start:" + start + " end:" + end);
28 
29         // search for right bound
30         start = 0;
31         end = A.length - 1;
32         while (start + 1 < end) {
33             mid = start + (end - start) / 2;
34             if (A[mid] == target)
35                 start = mid;
36             else if (A[mid] < target)
37                 start = mid;
38             else
39                 end = mid;
40         }
41 
42         System.out.println("right start:" + start + " end:" + end);
43                 //important : should judge end firstly
44         if (A[end] == target)
45             bound[1] = end;
46         else if (A[start] == target)
47             bound[1] = start;
48         else {
49             bound[0] = bound[1] = -1;
50             return bound;
51         }
52         return bound;
53     }54 }