배열의 검색 알고리즘은 무엇입니까?

배열 검색 알고리즘 모음: 선형 검색: 배열 탐색, 시간 복잡도 O(n). 이진 검색(순서 있는 배열만 해당): 배열을 두 개로 나누고 시간 복잡도는 O(log n)입니다. 해시 테이블: 키 값을 이용한 빠른 조회, 시간 복잡도 O(1).

배열 검색 알고리즘의 전체 목록

컴퓨터 과학에서 배열 검색 알고리즘은 순서가 있거나 순서가 없는 배열에서 특정 요소를 찾는 데 사용됩니다. 이 기사에서는 시간 복잡도와 실제 예제를 포함하여 다양한 배열 검색 알고리즘을 살펴봅니다.

선형 검색

시간 복잡도: O(n)

선형 검색은 가장 간단하고 직접적인 검색 알고리즘입니다. 배열의 처음부터 시작하여 대상 요소를 찾거나 배열의 끝에 도달할 때까지 요소를 하나씩 비교합니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!