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

题目要求

设计一个算法，输入为一个非递减顺序排列的整数数组 nums 和一个目标值 target。要求算法输出目标值 target 在数组 nums 中的起始位置和结束位置的索引。

如果数组中没有目标值 target，则输出 [-1, -1]。

算法的时间复杂度必须是 O(log n)，这意味着你需要使用比如二分查找这样的高效算法，而不是简单的线性扫描。

解题思路

由于题目要求算法的时间复杂度为 O(log n)，我们可以考虑使用二分查找算法。二分查找算法适用于有序数组，而题目中的数组已经是非递减顺序排列，满足使用二分查找的前提条件。

解题步骤如下：

1. 查找目标值的起始位置：通过修改二分查找的条件，当找到一个 target 时，不立即返回，而是继续在左侧区间查找，直到找到第一个 target 的位置。

2. 查找目标值的结束位置：同样使用二分查找，但这次当找到 target 时，继续在右侧区间查找，直到找到最后一个 target 的位置。

3. 返回结果：如果在第一步中没有找到 target，则说明数组中没有目标值，返回 [-1, -1]。如果找到了，返回起始位置和结束位置的索引。

注意事项：

• 在实现二分查找时，要正确处理查找区间的边界条件，确保不会漏掉目标值的起始位置和结束位置。
• 要确保算法的时间复杂度不超过 O(log n)，在每次查找时都应该是将查找区间减半，而不是逐个检查。
• 由于可能存在多个相同的 target 值，因此找到一个 target 后不能立即停止查找，需要继续查找以确定是否有相邻的相同值。

Golang 版本

func searchRange(nums []int, target int) []int {
    // 定义一个查找左边界的辅助函数
    findLeft := func() int {
        left, right := 0, len(nums)-1
        for left <= right {
            mid := left + (right-left)/2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid - 1
            } else {
                if mid == 0 || nums[mid-1] != target {
                    return mid
                }
                right = mid - 1
            }
        }
        return -1
    }

    // 定义一个查找右边界的辅助函数
    findRight := func() int {
        left, right := 0, len(nums)-1
        for left <= right {
            mid := left + (right-left)/2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid - 1
            } else {
                if mid == len(nums)-1 || nums[mid+1] != target {
                    return mid
                }
                left = mid + 1
            }
        }
        return -1
    }

    // 使用辅助函数查找左右边界
    left, right := findLeft(), findRight()

    // 如果左边界大于右边界，说明没有找到目标值
    if left > right {
        return []int{-1, -1}
    }
    return []int{left, right}
}

这段代码定义了两个辅助函数 findLeft 和 findRight 来分别查找目标值的起始位置和结束位置。主函数 searchRange 调用这两个函数，并根据返回的索引判断是否找到了目标值，最后返回结果数组。

C++版本

#include <vector>

class Solution {
public:
    std::vector<int> searchRange(std::vector<int>& nums, int target) {
        std::vector<int> result(2, -1); // 初始化结果为[-1, -1]

        // 辅助函数，用于查找左边界
        auto findLeft = [&](int target) -> int {
            int left = 0, right = nums.size() - 1, mid;
            while (left <= right) {
                mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    if (mid == 0 || nums[mid - 1] != target) {
                        return mid;
                    }
                    right = mid - 1;
                }
            }
            return -1;
        };

        // 辅助函数，用于查找右边界
        auto findRight = [&](int target) -> int {
            int left = 0, right = nums.size() - 1, mid;
            while (left <= right) {
                mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    if (mid == nums.size() - 1 || nums[mid + 1] != target) {
                        return mid;
                    }
                    left = mid + 1;
                }
            }
            return -1;
        };

        // 查找左边界
        result[0] = findLeft(target);
        // 如果左边界存在，则查找右边界
        if (result[0] != -1) {
            result[1] = findRight(target);
        }

        return result;
    }
};

这段 C++代码定义了一个名为 Solution 的类，其中包含一个 searchRange 方法，用于查找目标值 target 在数组 nums 中的起始和结束位置。它使用了两个 lambda 表达式 findLeft 和 findRight 来分别查找左边界和右边界。最后，根据查找结果返回一个包含两个元素的向量，如果没有找到目标值，则向量中的两个元素都是 -1。

Python 版本

from typing import List

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

        def findRight():
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    if mid == len(nums) - 1 or nums[mid + 1] != target:
                        return mid
                    left = mid + 1
            return -1

        left_idx = findLeft()
        right_idx = findRight()

        if left_idx == -1 or right_idx == -1:
            return [-1, -1]

        return [left_idx, right_idx]

# Example usage:
# nums = [5,7,7,8,8,10]
# target = 8
# sol = Solution()
# print(sol.searchRange(nums, target))  # Output: [3, 4]

这段 Python 代码定义了一个名为 Solution 的类，其中包含一个 searchRange 方法，用于查找目标值 target 在数组 nums 中的起始和结束位置。它定义了两个内部函数 findLeft 和 findRight 来分别查找左边界和右边界。最后，根据查找结果返回一个包含两个元素的列表，如果没有找到目标值，则列表中的两个元素都是 -1。

Java 版本

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1}; // 初始化结果数组

        // 查找左边界
        int leftIndex = findBoundary(nums, target, true);
        if (leftIndex == nums.length || nums[leftIndex] != target) {
            return result; // 如果左边界不存在，则直接返回[-1, -1]
        }
        result[0] = leftIndex; // 设置左边界
        result[1] = findBoundary(nums, target, false) - 1; // 设置右边界

        return result;
    }

    // 辅助函数，用于查找左边界或右边界
    private int findBoundary(int[] nums, int target, boolean left) {
        int low = 0;
        int high = nums.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > target || (left && nums[mid] == target)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return left ? low : high;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] range = solution.searchRange(nums, target);
        System.out.println("[" + range[0] + ", " + range[1] + "]");
    }
}

这段 Java 代码定义了一个名为 Solution 的类，其中包含一个 searchRange 方法，用于查找目标值 target 在数组 nums 中的起始和结束位置。它使用了一个辅助方法 findBoundary 来查找左边界或右边界，根据传入的布尔值 left 确定是查找左边界还是右边界。最后，根据查找结果返回一个包含两个元素的数组，如果没有找到目标值，则数组中的两个元素都是 -1。在 main 方法中，可以创建 Solution 的实例并调用 searchRange 方法来测试功能。

Rust 版本

fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
    fn find_boundary(nums: &Vec<i32>, target: i32, left: bool) -> i32 {
        let (mut low, mut high) = (0, nums.len() as i32);

        while low < high {
            let mid = low + (high - low) / 2;
            if nums[mid as usize] > target || (left && nums[mid as usize] == target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        low
    }

    let left_index = find_boundary(&nums, target, true);
    if left_index as usize == nums.len() || nums[left_index as usize] != target {
        return vec![-1, -1];
    }

    let right_index = find_boundary(&nums, target, false) - 1;
    vec![left_index, right_index]
}

fn main() {
    let nums = vec![5, 7, 7, 8, 8, 10];
    let target = 8;
    let range = search_range(nums, target);
    println!("[{}, {}]", range[0], range[1]);
}

这段 Rust 代码定义了一个 search_range 函数，它接受一个整数向量 nums 和一个整数 target 作为参数，并返回一个包含两个整数的向量，表示 target 在 nums 中的起始和结束位置。它使用了一个内部函数 find_boundary 来查找左边界或右边界。如果 target 在 nums 中不存在，则返回 [-1, -1]。在 main 函数中，可以调用 search_range 函数并打印结果来测试其功能。

总结

上面的 Rust 版本解法采用了二分查找算法来解决在排序数组中查找元素的起始和结束位置的问题。这种方法的时间复杂度为 O(log n)，符合题目要求的效率。解法的核心在于定义了一个辅助函数 find_boundary，它可以根据传入的参数决定是寻找左边界还是右边界。 find_boundary 函数接收三个参数：一个对数组的引用&Vec<i32>，目标值 target，以及一个布尔值 left，指示查找的是左边界还是右边界。函数内部使用二分查找的方式，根据 left 的值来调整查找的条件，从而找到目标值的边界。 在 search_range 函数中，首先调用 find_boundary 函数寻找左边界。如果找到的左边界超出数组范围或者对应的元素值不等于目标值，则说明目标值不存在于数组中，直接返回[-1, -1]。如果左边界存在，再次调用 find_boundary 函数寻找右边界，最后返回一个包含左右边界索引的向量。 在 main 函数中，通过实例化一个数组和目标值，调用 search_range 函数，并打印出返回的起始和结束位置，以此来验证函数的正确性。