数据结构查找算法代码
时间: 2024-05-28 11:07:28 浏览: 20
数据结构中的查找算法是指在数据集合中查找某个元素的过程。常见的查找算法包括顺序查找、二分查找、哈希查找等。以下是这些算法的介绍:
1. 顺序查找:从数据集合的第一个元素开始依次遍历,直到找到需要查找的元素或者遍历到集合的最后一个元素。时间复杂度为O(n)。
2. 二分查找:针对有序数据集合,将数据集合折半,每次将查找范围缩小一半,直到找到需要查找的元素或者确定该元素不存在。时间复杂度为O(logn)。
3. 哈希查找:通过哈希函数将元素的关键字转换为哈希值,将哈希值作为索引,在哈希表中进行查找。时间复杂度为O(1)。
以下是一个二分查找的代码示例(假设数组已经有序):
```
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
```
相关问题
数据结构查找算法的代码
数据结构中的查找算法是用于在给定数据集合中查找指定元素的算法。以下是几种常见的数据结构查找算法及其代码示例:
1. 线性查找算法(Linear Search):
线性查找算法是最简单的一种查找算法,它逐个比较数据集合中的元素,直到找到目标元素或遍历完整个集合。
代码示例:
```python
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1 # 如果未找到目标元素,返回-1
# 示例用法
arr = [5, 2, 9, 1, 7]
target = 9
result = linear_search(arr, target)
print("目标元素在数组中的索引为:", result)
```
2. 二分查找算法(Binary Search):
二分查找算法是一种高效的查找算法,要求数据集合必须是有序的。它通过将目标元素与数据集合的中间元素进行比较,并根据比较结果缩小查找范围,直到找到目标元素或确定不存在。
代码示例:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # 如果未找到目标元素,返回-1
# 示例用法
arr = [1, 2, 5, 7, 9]
target = 9
result = binary_search(arr, target)
print("目标元素在数组中的索引为:", result)
```
3. 哈希查找算法(Hash Search):
哈希查找算法利用哈希函数将数据映射到哈希表中的位置,通过查询哈希表来快速定位目标元素。
代码示例:
```python
def hash_search(hash_table, key):
hash_value = hash(key) % len(hash_table)
if hash_table[hash_value] == key:
return hash_value
else:
return -1 # 如果未找到目标元素,返回-1
# 示例用法
hash_table = [None] * 10
hash_table[3] = "apple"
hash_table[7] = "banana"
key = "banana"
result = hash_search(hash_table, key)
print("目标元素在哈希表中的位置为:", result)
`
数据结构二分查找算法代码
二分查找是一种基于比较目标值和数组中间元素的查找算法。在每次比较后,将查找范围缩小到数组的一半,直到找到目标值或者查找范围为空。
以下是二分查找算法的代码实现:
```c++
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
```
其中,arr是待查找的有序数组,left和right是查找范围的左右边界,target是目标值。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)