编写一个程序来实现二分搜索算法。如果找不到,则返回“无”,用python表示
时间: 2023-06-02 11:08:05 浏览: 57
以下是实现二分搜索算法的 Python 代码:
``` python
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
high = mid - 1
else:
low = mid + 1
return "无" # 如果没有找到,返回“无”
arr = [1,2,3,4,5,6,7,8,9]
target1 = 5
target2 = 10
print(binary_search(arr, target1)) # 输出:4
print(binary_search(arr, target2)) # 输出:无
```
注意:如果您在使用二分搜索算法时忘记先对数组排序,算法将无法正常工作。
相关问题
编写一个Python程序,实现一个简单的二分查找算法,输入一个有序的整数数组和一个目标值,程序输出目标值在数组中的索引位置(若不存在则输出-1)
好的,以下是简单的Python程序实现二分查找算法:
```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`表示输入的有序整数数组,`target`则表示目标值。程序使用了经典的二分查找算法,首先设定左右指针,然后在每次循环中计算中间位置并比较目标值与中间位置的值的大小关系,根据大小关系更新左右指针的位置。如果最终找到了目标值,则返回其在数组中的索引位置,否则返回-1表示目标值不存在于数组中。
你可以将上述代码复制到Python的交互式环境或者.py文件中运行,测试一下程序的正确性。
用Python程序编写出斐波那契二分检索,即使用斐波那契数列二分有序序列,查找某给定元素,找到返回下标,找不到返回-1
好的,下面是用 Python 编写的斐波那契二分检索算法:
```python
def fibonacci_search(arr, x):
"""
在有序序列 arr 中查找元素 x,返回其下标,找不到则返回 -1
"""
n = len(arr)
fib1, fib2 = 1, 1
while fib2 < n:
fib2, fib1 = fib1 + fib2, fib2
offset = 0
while fib2 > 1:
i = min(offset + fib1, n) - 1
if arr[i] < x:
fib2, fib1 = fib1, fib2 - fib1
offset = i
elif arr[i] > x:
fib2, fib1 = fib1 - fib2, fib1
else:
return i
if fib1 and arr[offset] == x:
return offset
return -1
```
其中,`arr` 为有序序列,`x` 为要查找的元素。首先,我们使用斐波那契数列生成两个相邻的斐波那契数,使得第二个斐波那契数恰好大于等于序列的长度。然后,我们使用指针 `offset` 记录当前的起始位置,不断缩小查找范围,直到找到元素或者无法继续缩小。如果找到元素,则返回其下标;否则,返回 -1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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_lunwen.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)