|
| 1 | +packageAlgorithms.binarySearch; |
| 2 | + |
| 3 | +publicclassSearchRange { |
| 4 | +publicstaticvoidmain(String[]strs) { |
| 5 | +int[]A = {1}; |
| 6 | + |
| 7 | +System.out.println(searchRange(A,0)[0] +" " +searchRange(A,0)[1]); |
| 8 | + } |
| 9 | + |
| 10 | +publicstaticint[]searchRange(int[]A,inttarget) { |
| 11 | +int[]ret = {-1, -1}; |
| 12 | + |
| 13 | +if (A ==null ||A.length ==0) { |
| 14 | +returnret; |
| 15 | + } |
| 16 | + |
| 17 | +intlen =A.length; |
| 18 | +intleft =0; |
| 19 | +intright =len -1; |
| 20 | + |
| 21 | +// so when loop end, there will be 2 elements in the array. |
| 22 | +// search the left bound. |
| 23 | +while (left <right -1) { |
| 24 | +intmid =left + (right -left) /2; |
| 25 | +if (target ==A[mid]) { |
| 26 | +// 如果相等，继续往左寻找边界 |
| 27 | +right =mid; |
| 28 | + }elseif (target >A[mid]) { |
| 29 | +// move right; |
| 30 | +left =mid; |
| 31 | + }else { |
| 32 | +right =mid; |
| 33 | + } |
| 34 | + } |
| 35 | + |
| 36 | +if (A[left] ==target) { |
| 37 | +ret[0] =left; |
| 38 | + }elseif (A[right] ==target) { |
| 39 | +ret[0] =right; |
| 40 | + }else { |
| 41 | +returnret; |
| 42 | + } |
| 43 | + |
| 44 | +left =0; |
| 45 | +right =len -1; |
| 46 | +// so when loop end, there will be 2 elements in the array. |
| 47 | +// search the right bound. |
| 48 | +while (left <right -1) { |
| 49 | +intmid =left + (right -left) /2; |
| 50 | +if (target ==A[mid]) { |
| 51 | +// 如果相等，继续往右寻找右边界 |
| 52 | +left =mid; |
| 53 | + }elseif (target >A[mid]) { |
| 54 | +// move right; |
| 55 | +left =mid; |
| 56 | + }else { |
| 57 | +right =mid; |
| 58 | + } |
| 59 | + } |
| 60 | + |
| 61 | +if (A[right] ==target) { |
| 62 | +ret[1] =right; |
| 63 | + }elseif (A[left] ==target) { |
| 64 | +ret[1] =left; |
| 65 | + }else { |
| 66 | +returnret; |
| 67 | + } |
| 68 | + |
| 69 | +returnret; |
| 70 | + } |
| 71 | +} |