Given a sorted array of n integers, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Example
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 if (A.length == 0) { 4 return new int[]{-1, -1}; 5 } 6 7 int start, end, mid; 8 int[] bound = new int[2]; 9 10 // search for left bound 11 start = 0; 12 end = A.length - 1; 13 while (start + 1 < end) { 14 mid = start + (end - start) / 2; 15 if (A[mid] == target) { 16 end = mid; 17 } else if (A[mid] < target) { 18 start = mid; 19 } else { 20 end = mid; 21 } 22 } 23 if (A[start] == target) { 24 bound[0] = start; 25 } else if (A[end] == target) { 26 bound[0] = end; 27 } else { 28 bound[0] = bound[1] = -1; 29 return bound; 30 } 31 32 // search for right bound 33 start = 0; 34 end = A.length - 1; 35 while (start + 1 < end) { 36 mid = start + (end - start) / 2; 37 if (A[mid] == target) { 38 start = mid; 39 } else if (A[mid] < target) { 40 start = mid; 41 } else { 42 end = mid; 43 } 44 } 45 if (A[end] == target) { 46 bound[1] = end; 47 } else if (A[start] == target) { 48 bound[1] = start; 49 } else { 50 bound[0] = bound[1] = -1; 51 return bound; 52 } 53 54 return bound; 55 } 56 }
原文：http://www.cnblogs.com/FLAGyuri/p/5370647.html