寻找目标值的起始和结束位置

题解思路

1. 观察题目特性

• 数组 nums 是 非递减排序 的，这意味着可以利用 二分查找 进行优化。
• 我们需要 找到目标值的左边界和右边界，可以使用 两次二分查找 分别确定。

2. 采用二分查找的方法

寻找左边界：

• 进行二分查找，如果 nums[mid] == target，则继续在左半部分查找，确保找到最左侧的 target。
• 终止条件是 left 指向 target 第一次出现的位置。

寻找右边界：

• 进行二分查找，如果 nums[mid] == target，则继续在右半部分查找，确保找到最右侧的 target。
• 终止条件是 right 指向 target 最后一次出现的位置。

复杂度分析

• 每次二分查找的时间复杂度为 $O(\log n)$，两次二分查找总共的时间复杂度仍然是 $O(\log n)$。
• 空间复杂度为 $O(1)$，因为我们仅使用了常数额外空间。

代码实现

Python 实现

import sys

def find_first_and_last(nums, target):
    # 寻找左边界
    def find_left():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:  # 继续向左找
                right = mid - 1
            else:
                left = mid + 1
        return left

    # 寻找右边界
    def find_right():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:  # 继续向左找
                right = mid - 1
            else:
                left = mid + 1
        return right

    left_index = find_left()
    if left_index >= len(nums) or nums[left_index] != target:
        return [-1, -1]

    right_index = find_right()
    return [left_index, right_index]

# 读取输入
n = int(sys.stdin.readline().strip())
if n == 0:
    print("-1 -1")
else:
    nums = list(map(int, sys.stdin.readline().split()))
    target = int(sys.stdin.readline().strip())

    result = find_first_and_last(nums, target)
    print(f"{result[0]} {result[1]}")

Java 实现

import java.util.Scanner;

public class Main {
    public static int[] searchRange(int[] nums, int target) {
        return new int[]{findLeft(nums, target), findRight(nums, target)};
    }

    // 找到 target 的左边界
    private static int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) { 
                right = mid - 1; // 继续向左找
            } else {
                left = mid + 1;
            }
        }
        return (left < nums.length && nums[left] == target) ? left : -1;
    }

    // 找到 target 的右边界
    private static int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) { 
                right = mid - 1; // 继续向左找
            } else {
                left = mid + 1;
            }
        }
        return (right >= 0 && nums[right] == target) ? right : -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n == 0) {
            System.out.println("-1 -1");
            return;
        }
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        int target = scanner.nextInt();
        int[] result = searchRange(nums, target);
        System.out.println(result[0] + " " + result[1]);
    }
}

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

// 找到左边界
int findLeft(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) { 
            right = mid - 1; // 继续向左找
        } else {
            left = mid + 1;
        }
    }
    return (left < nums.size() && nums[left] == target) ? left : -1;
}

// 找到右边界
int findRight(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) { 
            right = mid - 1; // 继续向左找
        } else {
            left = mid + 1;
        }
    }
    return (right >= 0 && nums[right] == target) ? right : -1;
}

// 主函数
int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << "-1 -1" << endl;
        return 0;
    }

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int target;
    cin >> target;

    int left = findLeft(nums, target);
    int right = findRight(nums, target);

    cout << left << " " << right << endl;
    return 0;
}

Leetcode 65.在排序数组中查找元素的第一个和最后一个位置-原题链接

题目内容

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

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

你必须设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题。

输入描述

• 第一行输入整数 $n$，表示数组的长度。
• 第二行输入 $n$ 个整数，表示数组 nums。
• 第三行输入一个整数 target，表示要查找的目标值。

输出描述

• 输出一行，包含两个整数，表示 target 在数组中的起始位置和结束位置。如果 target 不在数组中，则输出 -1 -1。

样例

样例 1

输入

6
5 7 7 8 8 10
8

输出

3 4

样例 2

输入

6
5 7 7 8 8 10
6

输出

-1 -1

提示

• $0 \leq n \leq 10^5$
• $-10^9 \leq nums[i] \leq 10^9$
• nums 是一个非递减数组
• $-10^9 \leq target \leq 10^9$