写一个代码,实现折半查找算法
时间: 2024-03-02 16:49:06 浏览: 35
好的,以下是 Python 代码实现折半查找算法:
```python
def binarySearch(arr, target):
"""
在有序数组 arr 中查找元素 target,返回其下标,若不存在则返回 -1
"""
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
```
其中,arr 表示有序数组,target 表示待查找元素。该函数通过不断缩小查找范围,最终找到目标元素或者判断其不存在,返回相应的下标或 -1。
相关问题
用c语言写一个代码,实现折半查找算法
好的,以下是 C 语言的折半查找算法代码:
```c
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中,arr 表示有序数组,n 表示数组长度,target 表示待查找元素。该函数通过不断缩小查找范围,最终找到目标元素或者判断其不存在,返回相应的下标或 -1。
如何实现折半查找算法
折半查找算法也称为二分查找算法,是一种常见的查找有序数组中元素的方法。其基本思路是将要查找的区间不断折半,缩小查找的范围,直到找到目标元素或者确定目标元素不存在。下面是折半查找算法的实现步骤:
1. 定义要查找的有序数组和目标元素;
2. 定义查找的起始位置 left 和结束位置 right,初始值为数组的首尾元素下标;
3. 计算中间位置 mid,取值为 (left + right) / 2;
4. 比较中间位置的元素和目标元素的大小关系:
- 如果中间位置的元素等于目标元素,返回 mid;
- 如果中间位置的元素小于目标元素,将查找范围缩小到右半部分,修改 left 为 mid + 1;
- 如果中间位置的元素大于目标元素,将查找范围缩小到左半部分,修改 right 为 mid - 1;
5. 重复步骤 3~4,直到找到目标元素或者确定目标元素不存在。
下面是使用 Python 语言实现折半查找算法的示例代码:
```python
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,nums 表示要查找的有序数组,target 表示目标元素。如果找到目标元素,返回其下标;否则返回 -1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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_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)