《アルゴリズムを学ぶ》3.線形探索

Overview

リストや配列から特定の値を見つける最も基本的な方法（線形探索）をまとめました。
1.線形探索の基本
2.線形探索の応用
3.線形探索の計算時間
4.典型問題を解いてみる

1. 線形探索の基本

リストの各要素を順番に確認し、目標の値があるかを判定する。

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 見つかったインデックスを返す
    return -1  # 見つからなければ -1

2. 線形探索の応用

複数の出現位置を記録

def find_all_indices(arr, target):
    return [i for i, num in enumerate(arr) if num == target]

最大/最小値を見つける

def find_max(arr):
    return max(arr)

def find_min(arr):
    return min(arr)

3. 線形探索の計算時間

線形探索は、先頭から順番に比較を繰り返す。そのため、データ数が多く、目的のデータが配列の後ろの方にある場合や目的のデータが存在しない場合には、比較回数が多くなり、時間がかかる。
計算時間はO(n)。(n = データ数)

データが多い場合はリストをソートして2分探索する方法などがある。（後日、ソートや2分探索は記事にします）

4. 典型問題を解いてみる

例題1. 特定の値の探索

問題: N 個の整数配列 A が与えられる。整数 X がリスト内にあるかどうかを判定せよ（Yes / No）。

参考： ABC315 B - Look for the Exact Number

回答　

N = int(input())
A = list(map(int, input().split()))
X = int(input())

print("Yes" if X in A else "No")

例題2. すべての出現位置を記録

問題: N 個の整数配列 A が与えられる。整数 X の出現位置をすべて出力せよ（1-indexed）。

参考： ABC302 B - Find Indexes

回答　

N = int(input())
A = list(map(int, input().split()))
X = int(input())

indices = [i+1 for i in range(N) if A[i] == X]
print(*indices if indices else [-1])

例題3. 最頻値の検索

問題: N 個の整数配列 A が与えられる。最も頻繁に出現する数を出力せよ。

参考： ABC317 B - Most Frequent Number

回答　

from collections import Counter

N = int(input())
A = list(map(int, input().split()))

counter = Counter(A)
most_common = counter.most_common(1)[0][0]
print(most_common)

例題4. 最大値と最小値の探索

問題: N 個の整数配列 A が与えられる。最大値と最小値を出力せよ。

参考： ABC320 B - Find Min and Max

回答　

N = int(input())
A = list(map(int, input().split()))

print(max(A), min(A))

例題5. 特定の条件を満たす数をカウント

問題: N 個の整数配列 A が与えられる。X 以上の数の個数を出力せよ。

参考： ABC321 C - Count Larger Numbers

回答　

N, X = map(int, input().split())
A = list(map(int, input().split()))

count = sum(1 for num in A if num >= X)
print(count)