题目难度： Medium
原题描述：
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].
题目大意：
给你一个非递减有序的数组和一个要查找的目标值，让你找到这个目标值在这个数组中的左边界和右边界，如果不存在目标值，则返回[-1,-1]。
解题思路：
这个问题是二分查找中经典的求上下界的问题，即找到目标值在一个有序数组中的范围。
首先是求左边界。在二分查找中，当target < nums[mid]时，target在数组中mid的左边，此时right = mid-1或right = mid都行。当target > nums[mid]时，target在数组中mid的右边，此时right = mid+1。当target == nums[mid]时，因为我们要找左边界，而mid以及mid左边的数都有可能存在target，因此right = mid。将第一和第三种情况统一，则当target <= nums[mid]时，right = mid。
然后是求右边界。要注意的是在求右边界时我们现在要求的是右边界的后一个位置，不然直接求右边界会出现死循环的问题。与求左边界类似，只是当target >= nums[mid]时，left = mid+1，当target < nums[mid]时，right = mid-1。而且此时while条件是left <= right。
时间复杂度分析：
算法使用两次二分查找，每次二分查找的时间复杂度为O(log(n))，因此总的时间复杂度为O(log(n))。
以下是代码：
public class Solution { public int lowerBound(int[] nums, int left , int right , int target){ while(left < right){ int mid = (left+right)/2; if(target <= nums[mid]){ right = mid; } else{ left = mid+1; } } return left; } public int upperBound(int[] nums, int left , int right , int target){ while(left <= right){ int mid = (left+right)/2; if(target >= nums[mid]){ left = mid+1; } else{ right = mid-1; } } return left; } public int[] searchRange(int[] nums, int target) { int len = nums.length; int leftBound = lowerBound(nums, 0, len-1, target); int rightBound = upperBound(nums, 0, len-1, target)-1; if(len==0 || nums[leftBound]!=target){ leftBound = rightBound = -1; } int a[] = {leftBound , rightBound}; return a; } }
