数组的搜索算法有哪些？

数组搜索算法大全：线性搜索：遍历数组，时间复杂度 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)

二分搜索用于在有序数组中搜索。它通过反复将数组分成两半来缩小搜索范围。

crmeb电商系统

CRMEB 是基于Thinkphp5基础开发的以会员为中心的电商系统，开源版微信公众号商城和小程序商城数据同步，带积分、优惠券、秒杀、砍价、分销等功能，更是一套方便二次开发的商城框架（后台封装了独有快速创建表单功能，无需写表单页面、快速创建数据搜索和数据列表页、导出表格、系统权限配置控制每一个控制器方法、系统参数配置、数据字典、组合数据等）

下载

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