配列の検索アルゴリズムは何ですか?

配列検索アルゴリズムのコレクション: 線形検索: 配列を走査し、時間計算量 O(n)。二分探索 (順序付けされた配列のみ): 配列を時間計算量 O(log n) の 2 つに分割します。ハッシュ テーブル: キー値を使用した高速ルックアップ、時間計算量 O(1)。

配列検索アルゴリズムの包括的なリスト

コンピューターサイエンスでは、配列検索アルゴリズムは、順序付き配列または順序なし配列内の特定の要素を見つけるために使用されます。この記事では、時間計算量や実際の例を含め、さまざまな配列検索アルゴリズムについて説明します。

線形探索

時間計算量: O(n)

線形探索は、最も単純かつ最も直接的な探索アルゴリズムです。配列の先頭から開始して、ターゲット要素が見つかるか配列の末尾に到達するまで、要素を 1 つずつ比較します。

def linear_search(arr, target):
  for i in range(len(arr)):
    if arr[i] == target:
      return i
  return -1

二分探索

時間計算量: O(log n)

二分探索は、順序付けされた配列内での検索に使用されます。配列を繰り返し半分に分割することで、検索範囲を絞り込みます。

def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1

ハッシュ テーブル

時間計算量: O(1)

ハッシュ テーブルは、キー値によって要素をすばやく見つけることができるデータ構造です。配列は、インデックスがキーとして使用されるハッシュ テーブルの基礎となるデータ構造として使用できます。

def hash_search(arr, target):
  hash_table = {}
  for i in range(len(arr)):
    hash_table[arr[i]] = i
  if target in hash_table:
    return hash_table[target]
  else:
    return -1

実践例

生徒のスコアを見つけるための次の配列検索の例を考えてみましょう:

students = [
  {'name': 'John Doe', 'score': 85},
  {'name': 'Jane Doe', 'score': 90},
  {'name': 'Bill Smith', 'score': 75},
  {'name': 'Alice Johnson', 'score': 95}
]

「Alice Johnson」のスコアを見つけたい場合は、線形検索を使用できます:

for student in students:
  if student['name'] == 'Alice Johnson':
    print(student['score'])  # 输出：95

あるいは、配列がソートされている場合名前で二分検索を使用できます:

students.sort(key=lambda x: x['name'])

left, right = 0, len(students) - 1
while left <= right:
  mid = (left + right) // 2
  if students[mid]['name'] == 'Alice Johnson':
    print(students[mid]['score'])  # 输出：95
    break
  elif students[mid]['name'] < 'Alice Johnson':
    left = mid + 1
  else:
    right = mid - 1

以上が配列の検索アルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。