编写一个Python程序,实现一个简单的二分查找算法,输入一个有序的整数数组和一个目标值,程序输出目标值在数组中的索引位置(若不存在则输出-1)
时间: 2024-03-12 11:47:51 浏览: 20
好的,以下是简单的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文件中运行,测试一下程序的正确性。
相关问题
4. 编写一个Python程序,实现一个简单的二分查找算法,输入一个有序的整数数组和一个目标值,程序输出目标值在数组中的索引位置(若不存在则输出-1)。
好的,以下是实现二分查找算法的Python程序:
```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
```
该程序接受两个参数,一个有序的整数数组 `arr` 和一个目标值 `target`。它使用 `low` 和 `high` 两个指针来确定要搜索的数组的区间,然后在每个迭代中计算 `mid` 指针,并将其与目标值进行比较。如果 `arr[mid]` 等于目标值,则返回 `mid`,否则根据 `arr[mid]` 与 `target` 的大小关系缩小搜索区间。如果最终未找到目标值,则返回 -1。
你可以将该程序保存为 `binary_search.py` 文件,并在命令行中使用以下命令运行它:
```
python binary_search.py
```
然后按照提示输入有序整数数组和目标值,程序将输出目标值在数组中的索引位置。
编写一个程序,实现对数组的顺序查找算法
以下是一个实现顺序查找算法的 Python 代码示例:
```python
def linear_search(arr, target):
"""
顺序查找算法
:param arr: 待查找的数组
:param target: 目标值
:return: 目标值在数组中的索引,若不存在则返回 -1
"""
n = len(arr)
for i in range(n):
if arr[i] == target:
return i
return -1
```
使用示例:
```python
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
result = linear_search(arr, target)
if result == -1:
print("目标值不存在!")
else:
print("目标值在数组中的索引为:", result)
```
输出结果:
```
目标值在数组中的索引为: 5
```
顺序查找算法的时间复杂度为 O(n),其中 n 为数组的长度。在最坏情况下,需要遍历整个数组才能确定目标值的位置,因此算法的效率较低。