原题链接在这里：https://leetcode.com/problems/search-for-a-range/
是Search Insert Position的变形，就是找边界情况。
这里一共做三次 二分查找，第一次试着找target, 若是找到了就存index在res 中，index对应的是边界还是中间的target 不重要。若是找不到直接返回res.
第二次找左边界，在 l = 0 和 target index 中间找，若是取得mid 位置上不等于target 说明左边界应该在后半部分找，若是等于target说明左边界应该在前半部找。
第三次找右边界，道理同上。Time Complexity O(logn), Space O(1).
AC Java:
1 public class Solution { 2 public int[] searchRange(int[] nums, int target) { 3 int [] res = {-1,-1}; 4 if(nums == null || nums.length == 0){ 5 return res; 6 } 7 //find target index 8 int l = 0; 9 int r = nums.length-1; 10 while(l<=r){ 11 int mid = l+(r-l)/2; 12 if(nums[mid] == target){ 13 res[0] = mid; 14 res[1] = mid; 15 break; 16 }else if (nums[mid] > target){ 17 r = mid-1; 18 }else{ 19 l = mid+1; 20 } 21 } 22 //if can‘t find target 23 if(res[0] == -1){ 24 return res; 25 } 26 l = 0; 27 r = nums.length -1; 28 int pos = res[0]; 29 //find the left bound 30 while(l<=pos){ 31 int mid = l+(pos-l)/2; 32 if(nums[mid] == target){ 33 pos = mid-1; 34 }else{ 35 l = mid+1; 36 } 37 } 38 res[0] = l; 39 40 //find the right bound 41 pos = res[1]; 42 while(pos<=r){ 43 int mid = pos + (r-pos)/2; 44 if(nums[mid] == target){ 45 pos = mid+1; 46 }else{ 47 r = mid-1; 48 } 49 } 50 res[1] = r; 51 return res; 52 } 53 }
还有第二种方法，只需要做两遍Binary Search.
第一遍用来找左边界，若是取mid 小于 target时，左边界会在后半部分，但是若mid 大于 或者 等于 target时左边界都会在前半部分。
第二遍用来找右边界，原理相同。
然后如何判断是否找到过target呢，若是找到了target, 那么ll 会在rr 的右侧，若是如此更改res结果，否则直接返回老的res。
1 public class Solution { 2 public int[] searchRange(int[] nums, int target) { 3 //Method 2 4 int [] res = {-1,-1}; 5 if(nums == null || nums.length == 0){ 6 return res; 7 } 8 //find left bound 9 int ll = 0; 10 int lr = nums.length - 1; 11 while(ll<=lr){ 12 int mid = ll+(lr-ll)/2; 13 if(nums[mid] < target){ 14 ll = mid+1; 15 }else{ 16 lr = mid-1; 17 } 18 } 19 //find right bound 20 int rl = 0; 21 int rr = nums.length - 1; 22 while(rl<=rr){ 23 int mid = rl+(rr-rl)/2; 24 if(nums[mid] <= target){ 25 rl = mid+1; 26 }else{ 27 rr = mid-1; 28 } 29 } 30 //check if target is found 31 if(ll>rr){ 32 return res; 33 } 34 res[0] = ll; 35 res[1] = rr; 36 return res; 37 } 38 }
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4881418.html