Search for a Range

Given an array of integers nums 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].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

这道题让我们在一个有序整数数组中寻找相同目标值的起始和结束位置，而且限定了时间复杂度为O(logn)，这是典型的二分查找法的时间复杂度，所以这道题我们也需要用此方法，我们的思路是首先对原数组使用二分查找法，找出其中一个目标值的位置，然后向两边搜索找出起始和结束的位置，可能有些人会觉得上面的算法不是严格意义上的O(logn)的算法，因为在最坏的情况下会变成O(n)，比如当数组里的数全是目标值的话，从中间向两边找边界就会一直遍历完整个数组，那么我们下面来看一种真正意义上的O(logn)的算法，使用两次二分查找法，第一次找到左边界，第二次调用找到右边界即可，具体代码如下：

第一点：在第一次调用二分法时，是找左边界，所以当nums[mid] ==target 时也让end = mid，是为了最后趋近左边界，反之在第二次调用二分法时，start保持位置不变，当nums[mid] == target时，让start = mid，是为了找右边界，所以让start不断往右push 第二点：因为这里用的二分法，start 和end 的用法是相邻就退出，所以每次确定边界的时候，必须start 和end的值都要确认一遍，因为不一定是哪一个

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1,-1};
        
        if(nums == null || nums.length == 0)
            return res;
        
        
        int start = 0, end = nums.length - 1;
        
        while(start + 1 < end){
            int mid = start + (end - start)/2;
            
            if(nums[mid] >= target){
                end = mid;
            }else{
                start = mid;
            }
        }
         
        if(nums[start] == target){
            res[0] = start;
        }
        else if(nums[end] == target){
            res[0] = end;
        }
            
        else
            return res;
        
        end = nums.length - 1;
        
        while(start + 1 < end){
            int mid = start + (end - start)/2;
            
            if(nums[mid] <= target){
                start = mid;
            }else{
                end = mid;
            }
        }
        
        System.out.println(nums[start] + " "+ nums[end]);
        
        if(nums[end] == target){
            res[1] = end;
        } 
        
        else if(nums[start] == target){
            res[1] = start;
        }
        
        return res;
        
        
    }
}