34. 在排序数组中查找元素的第一个和最后一个位置

问题

给定一个按照升序排列的整数数组 ，和一个目标值 。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是级别。

如果数组中不存在目标值，返回 。

示例 1:

输入:
输出:

示例 2:

输入:
输出:

解法

这个题乍一看就是二分查找的变种，考虑二分查找解决。
基本步骤如下：
使用二分法查找，假设与为数组起始位置与结束位置，有。此时，有三种情况会出现，我们首先排除掉的两种情况：

• 当时，;
• 当时，;
  接下来，我们考虑当时的情况处理，此时，代表所在位置肯定是位于返回结果的中间，那么，起始位置要么就是，要么肯定位于左侧，结束为止要么就是,要没肯定位于右侧。
  继续使用二分法处理，但是与传统二分法不太一样的地方在于，各元素计算的方式有些不同，如果凭感觉写不出的话，可以在纸上写几个模拟数组试一下就行了。

代码

java 实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        int[] result = new int[]{-1,-1};
        
        while (start <= end) {
            //首先需要二分法查询到nums[mid]==target的情况
            int mid = (start + end)/2;
            if (nums[mid] == target) {
                int temp = mid;
                while (start<mid) {
                    int ml = (start+mid)/2;
                    if (nums[ml] < target) {
                        start = ml+1;
                    } else {
                        mid = ml; 
                    }
                }
                result[0] = start;
                mid = temp;
                while (mid < end) {
                    int mr = (end + mid)/2 + 1;
                    if (nums[mr] >target) {
                        end = mr -1;
                    } else {
                        mid = mr;
                    }
                }
                result[1] = end;
                return result;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            
        }
        return result;
    }
}