Luogu P2249 【深基13.例1】查找 --- python 3解法

P2249 【深基13.例1】查找 - 洛谷

由于数据很大，建议使用sys模块加速读取

方法一：标准做法

import sys

def find_first(numbers, target):

    len_ = len(numbers)
    left = 0
    right = len_ - 1

    while left < right:
        mid = left + (right - left) // 2 # 防止溢出

        if numbers[mid] >= target:
            right = mid
        else:
            left = mid + 1
            
    # **检查是否找到目标**
    if left < len(numbers) and numbers[left] == target:
        return left + 1  # 从1开始编号
    else:
        return -1  # 目标不存在，返回 -1

def search_targets(numbers, ref):
    return [find_first(numbers, i) for i in ref] 

n, m =  map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
ref = list(map(int, sys.stdin.readline().split()))

print(' '.join(map(str,search_targets(numbers, ref))))

方法二：res[] -- 剪枝思想 -- 适用于查找重复元素

import sys

def find_first(numbers, target, res):
    # 如果已经计算过这个目标，直接从res取结果
    if target in res:
        return res[target]
    
    len_ = len(numbers)
    left = 0
    right = len_ - 1

    while left < right:
        mid = left + (right - left) // 2  # 防止溢出

        if numbers[mid] >= target:
            right = mid
        else:
            left = mid + 1

    # 检查是否找到目标
    if left < len(numbers) and numbers[left] == target:
        res[target] = left + 1  # 从1开始编号
        return res[target]
    else:
        res[target] = -1  # 目标不存在，返回 -1
        return -1

def search_targets(numbers, ref):
    res = {}  # 使用字典来存储已经查找过的目标元素的索引
    return [find_first(numbers, i, res) for i in ref]

# 读取输入
n, m = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
ref = list(map(int, sys.stdin.readline().split()))

# 输出结果
print(' '.join(map(str, search_targets(numbers, ref))))