用python写折半查找算法,算法描述如下: (1) 将数组或列表有序排列。 (2) 设置左指针 left = 0,右指针 right = len(array) - 1。 (3) 计算中间指针 mid = (left + right) // 2。 (4) 如果中间指针所指元素等于目标值,则返回 mid。 (5) 如果中间指针所指元素大于目标值,则在左半区间继续搜索,right = mid - 1。 (6) 如果中间指针所指元素小于目标值,则在右半区间继续搜索,left = mid + 1。 (7) 重复步骤 3-6,直到找到目标元素或区间为空。 (8) 如果区间为空也未找到目标值,则返回 -1。
时间: 2024-03-09 16:51:03 浏览: 22
下面是用 Python 实现的折半查找算法:
```python
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:
right = mid - 1
else:
left = mid + 1
return -1
```
其中,`arr` 是有序数组,`target` 是要查找的目标值。函数返回目标值在数组中的索引,如果没有找到则返回 -1。
相关问题
使用python编写折半查找算法,算法描述如下: (1) 将数组或列表有序排列。 (2) 设置左指针 left = 0,右指针 right = len(array) - 1。 (3) 计算中间指针 mid = (left + right) // 2。 (4) 如果中间指针所指元素等于目标值,则返回 mid。 (5) 如果中间指针所指元素大于目标值,则在左半区间继续搜索,right = mid - 1。 (6) 如果中间指针所指元素小于目标值,则在右半区间继续搜索,left = mid + 1。 (7) 重复步骤 3-6,直到找到目标元素或区间为空。 (8) 如果区间为空也未找到目标值,则返回 -1。
以下是使用Python编写的折半查找算法:
```python
def binary_search(array, target):
"""
在有序数组array中查找目标元素target,返回其下标。
如果未找到则返回-1。
"""
left, right = 0, len(array) - 1
while left <= right:
mid = (left + right) // 2 # 计算中间位置
if array[mid] == target:
return mid # 找到目标元素,返回下标
elif array[mid] > target:
right = mid - 1 # 目标元素在左半区间
else:
left = mid + 1 # 目标元素在右半区间
return -1 # 未找到目标元素,返回-1
```
函数接受一个有序数组array和一个目标元素target作为参数。函数首先将左指针left设为0,右指针right设为数组长度减1。然后,在每次循环中计算中间位置mid,如果array[mid]等于目标元素target,则返回mid;如果array[mid]大于target,则说明目标元素在左半区间,将右指针right设为mid-1;如果array[mid]小于target,则说明目标元素在右半区间,将左指针left设为mid+1。如果循环结束后仍未找到目标元素,则返回-1。
用python实现折半查找算法,算法描述如下: (1)将数组或列表有序排列。 (2)设置左指针left=0,右指针right=len(array)-1。 (3)计算中间指针mid=(left+right)//2。(4)如果中间指针所指元素等于目标值,则返回mid。 (5)如果中间指针所指元素大于目标值,则在左半区间继续搜索,right= mid-1。 (6)如果中间指针所指元素小于目标值,则在右半区间继续搜索,left= mid+1。 (7)重复步骤3-6,直到找到目标元素或区间为空。 (8)如果区间为空也未找到目标值,则返回-1。
好的,以下是Python实现折半查找算法的代码:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1 # 设置左右指针
while left <= right:
mid = (left + right) // 2 # 计算中间指针
if arr[mid] == target: # 如果中间指针所指元素等于目标值,则返回mid
return mid
elif arr[mid] > target: # 如果中间指针所指元素大于目标值,则在左半区间继续搜索
right = mid - 1
else: # 如果中间指针所指元素小于目标值,则在右半区间继续搜索
left = mid + 1
return -1 # 如果区间为空也未找到目标值,则返回-1
# 测试代码
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
print(binary_search(arr, target)) # 输出 5
```
这段代码使用了循环的方式实现折半查找算法。首先设置左右指针,然后计算中间指针。如果中间指针所指元素等于目标值,则返回中间指针;如果中间指针所指元素大于目标值,则在左半区间继续搜索,将右指针向中间指针左边移动一位;如果中间指针所指元素小于目标值,则在右半区间继续搜索,将左指针向中间指针右边移动一位。然后重复以上步骤,直到找到目标元素或区间为空。如果区间为空也未找到目标值,则返回-1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)