数据结构中的查找代码
时间: 2024-06-22 13:03:41 浏览: 8
在数据结构中,查找(也称为搜索)通常是算法的核心部分,涉及到在给定的数据集合中找到特定元素的过程。常见的查找算法有以下几种:
1. **顺序查找**(Sequential Search):线性扫描数组或列表,逐个比较元素,直到找到目标或遍历完整个序列。时间复杂度为 O(n)。
```python
def sequential_search(array, target):
for i in range(len(array)):
if array[i] == target:
return i
return -1
```
2. **二分查找**(Binary Search):适用于有序数组,每次将查找区间缩小一半。时间复杂度为 O(log n)。
```python
def binary_search(array, target):
left, right = 0, len(array) - 1
while left <= right:
mid = (left + right) // 2
if array[mid] < target:
left = mid + 1
elif array[mid] > target:
right = mid - 1
else:
return mid
return -1
```
3. **哈希表查找**(Hash Table):使用哈希函数将键映射到存储位置,常数时间内完成查找。平均时间复杂度为 O(1),但在最坏情况下可能退化为 O(n)。
```python
def hash_table_search(hash_table, key):
if key in hash_table:
return hash_table[key]
else:
return None
```
4. **关联数组查找**(Dictionary-Based Search):类似哈希表,通过键值对快速查找,时间复杂度为 O(1)。
```python
def associative_array_search(dictionary, key):
if key in dictionary:
return dictionary[key]
else:
return None
```
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)