What are the search algorithms for arrays?

Comprehensive list of array search algorithms: linear search: traverse the array, time complexity O(n). Binary search (ordered array only): Divide the array into two, time complexity O(log n). Hash table: fast lookup using key value, time complexity O(1).

Comprehensive list of array search algorithms

In computer science, array search algorithms are used to find specific elements in an ordered or unordered array. This article will explore various array search algorithms, including their time complexity and practical examples.

Linear search

Time complexity: O(n)

Linear search is the simplest and most direct search algorithm. It starts from the beginning of the array and compares elements one by one until it finds the target element or reaches the end of the array.

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

Binary search

Time complexity: O(log n)

Binary search is used to search in an ordered array. It narrows the search by repeatedly splitting the array in half.

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

Hash table

Time complexity: O(1)

A hash table is a data structure that allows us to pass a key Quickly find elements by value. Arrays can be used as the underlying data structure for hash tables, where the index is used as the key.

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

Practical case

Consider the following array search case to find student scores:

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

If we want to find the score of "Alice Johnson", we can use linear search:

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

Alternatively, if the array is sorted by name, we can use a binary search:

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

The above is the detailed content of What are the search algorithms for arrays?. For more information, please follow other related articles on the PHP Chinese website!