思路：

题意很明显了，要使用二分搜索在O(lgn)时间内找到第一次出现和最后一次出现的目标下标，如果没有出现，则返回-1。

一直以来都只会写最基本的二分查找（找到就停那种），要么就是为了省事直接用Arrays.binarySearch(arr, target);

这次自己写了下，感觉也不是很难。

 

在最基本的版本上增加两个东西：

1. 不是找到就停，而是继续压缩查找空间。first就压缩上界；last就压缩下界。

2. 由于不知道何时停止，需要一个变量ind来不断更新target对应的下标。

 

1 class Solution { 2     public int[] searchRange(int[] nums, int target) { 3         // return new int[]{firstBinarySearch(nums, target), 4         //                 lastBinarySearch(nums, target)}; 5         return new int[]{specialBinarySearch(nums, target, true), 6                         specialBinarySearch(nums, target, false)}; 7     } 8      9     public int firstBinarySearch(int[] nums, int target) {10         int low = 0, high = nums.length - 1;11         int ind = -1;12         while (low <= high) {13             int mid = (low + high) / 2;14             if (nums[mid] < target)15                 low = mid + 1;16             else{17                 ind = nums[mid] == target ? mid : ind;18                 high = mid - 1;19             }   20         }21         return ind;22     }23     24     public int lastBinarySearch(int[] nums, int target) {25         int low = 0, high = nums.length - 1;26         int ind = -1;27         while (low <= high) {28             int mid = (low + high) / 2;29             if (nums[mid] > target)30                 high = mid - 1;31             else{32                 ind = nums[mid] == target ? mid : ind;33                 low = mid + 1;34             }   35         }36         return ind;37     }38     39     public int specialBinarySearch(int[] nums, int target, boolean isFirst) {40         int low = 0, high = nums.length - 1;41         int ind = -1;42         while (low <= high) {43             int mid = (low + high) / 2;44             if (nums[mid] < target)45                 low = mid + 1;46             else if (nums[mid] > target)47                 high = mid - 1;48             else {49                 ind = mid;50                 high = isFirst ? mid - 1 : high;51                 low = !isFirst ? mid + 1 : low;52             }53         }54         return ind;55     }56 }

 

这里还写了一个最终版本specialBinarySearch，将两种情况合并到一起判断。是不是和原来的基础版很接近？