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

This question looks very much like the binary search problem. But we may have multiple target values, and we need to find the first position and the last position of that. What should we do? An insight just come to mind is that we should find the last number that is smaller than the target, as well as the first number that is greater than the target. They are found by the functions of bsearchlower() and bsearchupper() respectively. We call this pair of indexes "left" and "right". When we find them, we should check whether A[++left] equals the target value. If it is, we then check whether A[--right] equals the target value. and than the left, right will be the index we want to return. Otherwise the target does not exist in the array and we just return [-1,-1].

Java: SearchInARange

01 public int[] searchRange(int[] A, int target) {
02     int[]result=new int[2];
03     int lo=0;
04     int hi=A.length-1;
05     if(A[hi]<target ||A[lo]>target )
06     {
07         result[0]=-1;
08         result[1]=-1;
09         return result;
10     }
11     int left=bsearchlower(A,target,lo,hi);
12     if(A[left]<target)
13         left=left+1;      
14     if(A[left]==target)
15     {
16         result[0]=left;
17         int right=bsearchupper(A,target,lo,hi);
18         if(A[right]>target)      
19             right=right-1;      
20         if(A[right]==target)
21             result[1]=right;        
22         else
23         {
24             result[0]=-1;
25             result[1]=-1;                          
26         }          
27     }
28   
29     else
30     {
31         result[0]=-1;
32         result[1]=-1;                      
33     }      
34     return result;      
35 }
36 
37 //Find the last number that is smaller than target
38 public int bsearchlower(int [] A, int target, int lo, int hi)
39 {
40     if(lo>hi||target<A[lo]||target>A[hi])
41     {
42         return -1;
43     }
44     int mid=(lo+hi+1)/2;
45     while(lo<hi)
46     {
47         if(A[mid]<target)
48         {
49             lo=mid;
50         }
51         else
52         {
53             hi=mid-1;
54         }
55         mid=(lo+hi+1)/2;
56     }
57     return mid;
58 }
59 
60 //Find the first number that is greater than target
61 public int bsearchupper(int[] A, int target, int lo, int hi)
62 {
63     if(lo>hi ||target<A[lo]||target>A[hi])
64     {
65         return -1;
66     }
67     int mid=(lo+hi)/2;
68     while(lo<hi)
69     {
70         if(A[mid]>target)
71         {
72             hi=mid;
73         }
74         else
75         {
76             lo=mid+1;
77         }
78         mid=(lo+hi)/2;
79     }
80     return mid;
81 }