题目：
Given an array of integers sorted in ascending order, 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].
题意：给出一个升序排列的数组，其中可能有重复的元素。给出一个target，在数组中查找，若查找到则返回数组中该元素开始的坐标和结束的index(如果其中只有一个元素匹配，则返回的开始和结束index相同,例如[3,3])；若不存在则返回[-1,-1]。我采用的方法是直接对数组进行二分查找，若查找到元素，则对该位置分别向前和向后查找，直到和target不相等；如没有查找到元素则直接返回[-1，-1]. 但是这样做的最差复杂度为0(n)，所以可以使用两个二分查找分别查找最左的target和最右的target，然后相减即可。
代码：
public int[] searchRange(int[] A, int target) { int [] res = {-1,-1}; if(A == null || A.length == 0) return res; //first iteration, find target wherever it is int low = 0; int high = A.length-1; int pos = 0; while(low <= high){ int mid = (low + high)/2; pos = mid; if(A[mid] > target) high = mid - 1; else if(A[mid] < target) low = mid + 1; else{ res[0] = pos; res[1] = pos; break; } } if(A[pos] != target) return res; //second iteration, find the right boundary of this target int newlow = pos; int newhigh = A.length-1; while(newlow <= newhigh){ int newmid = (newlow+newhigh)/2; if(A[newmid] == target) newlow = newmid + 1; else newhigh = newmid - 1; } res[1] = newhigh; //third iteration, find the left boundary of this target newlow = 0; newhigh = pos; while(newlow <= newhigh){ int newmid = (newlow+newhigh)/2; if(A[newmid] == target) newhigh = newmid - 1; else newlow = newmid + 1; } res[0] = newlow; return res; }