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

题目描述

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

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例1：

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例2：

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

思路

1.从本题的时间复杂度来看，肯定是要使用二分搜索算法。
2.我们可以使用两次二分搜索算法，第一次查询左边的索引，第二次查询右边的索引。
3.注意处理边界值，不越界就好啦。

Java代码实现

   public int[] searchRange(int[] nums, int target) {
        int leftIndex = -1;
        int rightIndex = -1;

        int left = 0;
        int right = nums.length-1;

        //先找左边
        while(left <= right){
            int mid = (left+right)/2;
            if(nums[mid]<target){
                left = mid + 1;
            }else if(nums[mid]>target){
                right = mid - 1;
            }else{
                if(mid == 0 || nums[mid-1] != nums[mid]){
                    leftIndex = mid;
                    break;
                }else {
                    right = mid - 1;
                }
            }
        }

        left = 0;
        right = nums.length-1;

        //再找右边
        while(left <= right){
            int mid = (left+right)/2;
            if(nums[mid]<target){
                left = mid + 1;
            }else if(nums[mid]>target){
                right = mid - 1;
            }else{
                if(mid == nums.length-1 || nums[mid+1] != nums[mid]){
                    rightIndex = mid;
                    break;
                }else {
                    left = mid + 1;
                }
            }
        }

        return new int[]{leftIndex,rightIndex};
    }

Golang代码实现

func searchRange(nums []int, target int) []int {
    left,right := 0,len(nums)-1
    leftIndex,rightIndex := -1,-1
    //先找左边
    for left <= right  {
        mid := (left+right)/2
        if nums[mid] == target{
            if mid == 0 || nums[mid-1] != nums[mid] {
                leftIndex = mid
                break
            }else{
                right = mid-1
            }
        } else if nums[mid] > target{
            right = mid-1
        } else{
            left = mid+1
        }
    }

    left,right = 0,len(nums)-1
    //再找右边
    for left <= right {
        mid := (left+right)/2
        if nums[mid] == target{
            if mid == len(nums)-1 || nums[mid+1] != nums[mid] {
                rightIndex = mid
                break
            }else{
                left = mid+1
            }
        } else if nums[mid] > target{
            right = mid-1
        } else{
            left = mid+1
        }
    }

    return []int{leftIndex,rightIndex}
}