数据结构折半查找代码
时间: 2023-06-28 17:14:51 浏览: 51
以下是使用C语言实现的折半查找代码:
```c
int binarySearch(int arr[], int n, int x) {
int left = 0, right = n - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(arr[mid] == x) {
return mid;
} else if(arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中 `arr` 是要查找的数组,`n` 是数组的大小,`x` 是要查找的元素。这个函数会在已经排序的数组中查找元素 `x`,如果找到了则返回该元素在数组中的下标,否则返回 -1。该算法的时间复杂度为 O(log n)。
相关问题
数据结构折半查找实验代码
以下是 Python 3 实现的折半查找算法代码:
```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
```
使用方法:
```python
arr = [1, 3, 5, 7, 9]
target = 5
index = binary_search(arr, target)
print(index) # 输出 2
```
说明:以上代码中的 `arr` 表示要进行查找的有序数组,`target` 表示要查找的目标值,`binary_search` 函数返回目标值在数组中的下标,如果不存在则返回 -1。
数据结构折半查找练习
当然,我可以帮助你练习折半查找算法。折半查找也被称为二分查找,它是一种高效的查找算法,适用于有序数组。
首先,让我们来了解一下折半查找的步骤:
1. 确定要查找的目标值。
2. 初始化左边界(left)为数组的第一个元素的索引,右边界(right)为数组的最后一个元素的索引。
3. 计算中间元素的索引(mid),可以使用公式 `mid = (left + right) // 2`。
4. 比较中间元素与目标值:
- 如果中间元素等于目标值,返回中间元素的索引。
- 如果中间元素大于目标值,将右边界更新为mid-1,重复步骤 3。
- 如果中间元素小于目标值,将左边界更新为mid+1,重复步骤 3。
5. 重复步骤 3 和步骤 4,直到找到目标值或者左边界大于右边界。
下面是一个示例代码实现折半查找:
```python
def binary_search(arr, target):
left = 0
right = 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 # 目标值不存在
# 示例用法
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
print(f"目标值 {target} 在数组中的索引为 {result}")
else:
print("目标值不存在于数组中")
```
你可以尝试使用不同的有序数组和目标值测试该算法。如果有任何问题,请随时向我提问。