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

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

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

思路分析

等于给定值的第一个元素和最后一个元素

由于数组是排序的，我们可以利用二分查找来高效地找到目标值的第一个和最后一个位置。

查找第一个位置：

使用二分查找，找到 target 的第一个出现位置。

如果 mid 位置的值等于 target，则继续向左查找（即 right = mid - 1），以确保找到第一个位置。

如果 mid 位置的值小于 target，则向右查找（即 left = mid + 1）。

查找最后一个位置：

使用类似的二分查找，找到 target 的最后一个出现位置。

如果 mid 位置的值等于 target，则继续向右查找（即 left = mid + 1），以确保找到最后一个位置。

如果 mid 位置的值大于 target，则向左查找（即 right = mid - 1）。

参考代码

// 查找元素的第一个和最后一个位置
func searchRange(nums []int, target int) []int {
	first := findFirstPosition(nums, target)
	last := findLastPosition(nums, target)
	return []int{first, last}
}

// 查找第一个位置
func findFirstPosition(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1

	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			res = mid
			right = mid - 1 // 继续向左查找
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return res
}

// 查找最后一个位置
func findLastPosition(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1

	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			res = mid
			left = mid + 1 // 继续向右查找
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return res
}

🍏 点击查看 Java 题解

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

    public int searchLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int first = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                first = mid;
                right = mid - 1;
            }
        }
        return first;
    }

    public int searchRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int last = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                last = mid;
                left = mid + 1;
            }
        }
        return last;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/81925119