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

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

• 1. 题目描述
• 2.详细题解
• • （1）朴素二分查找算法
  • （2）改进二分查找算法
• 3.代码实现
• • 3.1 Python
  • •   方法一:
    •   方法二:
    •   方法三：优化方法二
  • 3.2 Java

1. 题目描述

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

2.详细题解

（1）朴素二分查找算法

    在非递减（升序）数组中查找目标值的起始和结束位置，如果不存在则返回[-1,-1]，最直观和直接的方法是依次遍历，第一次寻找到的位置为起始位置，记录下状态，当数组已遍历完或者遍历到非目标值时，此时上一个位置即为结束位置，时间复杂度为 O ( n ) O(n) O(n)，该方法未利用数组有序的条件，典型的二分查找算法，但有一定的变型。
  朴素的二分查找算法，使用传统意义的算法，但当中间值等于目标值时，此时再分别向左和向右扩展，即可找到起始位置和结束位置。此时，最坏情况下的时间复杂度仍然为 O ( n ) O(n) O(n)，例如全为目标值组成的数列，如[7,7,7,7,7,7,7]，此时仍然要遍历全数组，且还多了二分查找的时间。具体代码实现见Python实现方法一。

（2）改进二分查找算法

  同69. x 的平方根（简单）类似，本质上均属于相同类型的二分查找变型题，在69. x 的平方根（简单）中，寻找算术平方根的整数部分，因此相当于寻找首次大于指定数的整数，该整数减 1 1 1即为所求值，即右指针值。
  针对本题，对于目标值的起始位置和结束位置，可以分别使用二分查找算法寻找。

• 对于结束位置，寻找最后一个目标值的索引，相当于寻找首次大于目标值的索引，减 1 1 1即可，此时同69. x 的平方根（简单）一致，右指针当中间值大于目标值即会更新为 r i g h t = m i d − 1 right=mid-1 right=mid−1，即 r i g h t right right指针完整的记录下来了最后一个目标值的索引。（满足大于目标值才会更新right的值，因此最终right保留的为最后一次大于目标值的中间值，该中间值即为首次大于目标值的索引，而 r i g h t = m i d − 1 right=mid-1 right=mid−1，即 r i g h t right right指针为结束位置。）

• 对于起始位置，寻找第一个目标值的索引，相当于寻找在目标值出现之前，最后一个不为目标值的索引，加 1 1 1即可，稍微改变下寻找结束位置索引时的寻找条件，因为需要寻找第一个目标值出现前一个位置的索引，那么当中间值大于等于时即更新 r i g h t = m i d − 1 right=mid-1 right=mid−1，此时 r i g h t right right指针完整的记录下来了在目标值出现之前，最后一个不为目标值的索引，此时加 1 1 1即为起始位置的索引。（满足大于等于目标值才会更新 r i g h t right right值 ，故 r i g h t right right记录的是最后一个大于等于目标值的索引，而 r i g h t right right有减1，因此加1即为起始位置。）

• 需要注意的时， r i g h t right right指针记录的不一定是真实的目标值的起始或结束位置的索引，当未找到目标值的时候，程序循环也会结束，因为需要判断找到的起始或者结束位置是否在索引范围内，或者是否目标值，否则返回-1。

  具体代码实现见Python实现方法二。但需要注意的时，此时二分查找起始和结束位置代码冗余度过高，因此可以进一步优化降低代码冗余度，具体代码实现见Python实现方法三。
  Java代码实现直接给出最终优化后算法的实现，见Java实现。

3.代码实现

3.1 Python

  方法一:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l, r = -1, -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                l, r = mid, mid
                while l - 1 >= 0 and nums[l-1] == target:
                    l -= 1
                while r + 1 < len(nums) and nums[r+1] == target:
                    r += 1
                break
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return [l, r]
        

  方法二:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binaeySearchRight(nums, target):
            left, right = 0, len(nums) -1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            if right < 0 or nums[right] != target:
                right = -1
            return right
        def binaeySearchLeft(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left +right) // 2
                if nums[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1
            right += 1
            if right >= len(nums) or nums[right] != target:
                right = -1
            return right
        left = binaeySearchLeft(nums, target)
        right = binaeySearchRight(nums, target)
        return [left, right]

  方法三：优化方法二

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binaeySearch(nums, target, direction=True):
            # 规定：True表示查找起始位置，否则查找结束位置
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] > target or (direction and nums[mid] >= target):
                    right = mid - 1
                else:
                    left = mid + 1
            if direction:
                right += 1
            if right < 0 or right >= len(nums) or nums[right] != target:
                right = -1
            return right

        left = binaeySearch(nums, target, True)
        right = binaeySearch(nums, target, False)
        return [left, right]

3.2 Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = binarySearch(nums, target, true);
        int right = binarySearch(nums, target, false);
        return new int[]{left, right};

    }
    public int binarySearch(int[] nums, int target, boolean direction){
        //规定：True表示查找起始位置，否则查找结束位置
        int left = 0, right = nums.length - 1;
        while (left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] > target || (direction && nums[mid] >= target)){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        if (direction){right++;}
        if (right < 0 || right >= nums.length || nums[right] != target){right=-1;}
        return right;
    }
}

  执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code。