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].
思路
通过二分查找，如果没找到返回[-1,-1]如果找到middle，找出start和ending即可
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 boolean found = false; 4 int low = 0; 5 int high = A.length - 1; 6 int middle = 0; 7 int result[] = new int[2]; 8 9 while(low <= high){ 10 middle = (low + high) / 2; 11 if(target > A[middle]){ 12 low = middle + 1; 13 } 14 else if(target < A[middle]){ 15 high = middle - 1; 16 } 17 else 18 { 19 found = true; 20 break; 21 } 22 }//while 23 if(!found) //没有查找到 24 { 25 result[0] = -1; 26 result[1] = -1; 27 }//if 28 else{ 29 while(middle >= 0 && A[middle] == target){ 30 middle--; 31 } 32 if(middle < 0) 33 result[0] = 0; 34 else 35 result[0] = middle + 1; 36 middle = result[0]; 37 while(middle < A.length && A[middle] == target){ 38 middle++; 39 } 40 if(middle >= A.length) 41 result[1] = A.length - 1; 42 else 43 result[1] = middle - 1; 44 }//else 45 return result; 46 } 47 }